כל פקודה תתחיל ב-MKגדולות עש מיכאל קלי (Michael Kali), וזאת משתי סיבות:
כדי שבטבלת הקיצורים שבתוך \SpecialChar LyX תופענה כל הפקודות זו לצד זו.
הבחירה דווקא באותיות גדולות נועדה לוודא שהפקודות אינן מתנגשות עם פקודות \SpecialChar LaTeX מקוריות.
על הפקודות להיות קצרות ככל האפשר, וזאת כדי לאפשר את כתיבתן במהירות מבלי ליצור להן קיצור מקלדת. הסיבה לכך שלא ניצור קיצור מקלדת לכל פקודה היא שפעמים רבות ניצור פקודות שתיועדנה למקרים מסוימים מאוד, ואז יעבור זמן רב עד שנשתמש בקיצור המקלדת בפעם הבאה ולכן לא נזכור אותו - הרבה יותר פשוט לזכור את הפקודה שיצרנו מכיוון שיש לה תוכן אמיתי שקשור לפלט הרצוי מן הפקודה. סיבה נוספת היא שיצירת קיצור מקלדת לכל פקודה ולו החריגה ביותר תקשה עלינו ליצור קיצורי מקלדת לפקודות חשובות יותר. לפיכך פקודות שימושיות מאוד שבוודאי ניצור להן קיצור מקלדת ונשתמש בו פעמים רבות אינן צריכות להיות קצרות.
כדי להקל על כתיבת פקודות שלא יצרתי להן קיצור מקלדת כתבתי קיצור מקלדת שיוצר את הקידומת של כל פקודות ה-macrosשלי ואז כל מה שנותר הוא להקיש שלוש-ארבע אותיות כדי לבחור את הפקודה הרצויה, קיצור המקלדת המדובר הוא "Ctrl+k".
לכל גופן יש קידומת בת שתי אותיות.
\(\:\)
\(\:\)קבוצות ופונקציות לפי קורסיםLatexCommand ruleoffset "0.5ex"width "100col%"height "1pt"\(\:\)
\(\:\)המספרים המרוכבים ופונקציות מרוכבות\(\:\)
\(\newcommand{\MKcis}{\text{cis}}\)\(\cos+i\cdot\sin\). המספרים המרוכבים.
\(\newcommand{\MKre}{\text{Re}}\)החלק הממשי של מספר מרוכב. המספרים המרוכבים.
\(\newcommand{\MKim}{\text{Im}}\)החלק המדומה של מספר מרוכב. המספרים המרוכבים.מופיע גם כתמונה של פונקציה.
\(\:\)גופןmathcal: בסיסים, קבוצת חזקה, העתקות גלואה, המילטוניאן ועוד\(\:\)
\(\newcommand{\MKcla}{\mathcal{A}}\)
\(\newcommand{\MKclb}{\mathcal{B}}\)
\(\newcommand{\MKclc}{\mathcal{C}}\)
\(\newcommand{\MKcld}{\mathcal{D}}\)
\(\newcommand{\MKcle}{\mathcal{E}}\)
\(\newcommand{\MKclf}{\mathcal{F}}\)
\(\newcommand{\MKclg}{\mathcal{G}}\)
\(\newcommand{\MKclh}{\mathcal{H}}\)
\(\newcommand{\MKcli}{\mathcal{I}}\)
\(\newcommand{\MKclj}{J}\)
\(\newcommand{\MKclk}{\mathcal{K}}\)
\(\newcommand{\MKcll}{\mathcal{L}}\)
\(\newcommand{\MKclm}{\mathcal{M}}\)
\(\newcommand{\MKcln}{\mathcal{N}}\)
\(\newcommand{\MKclo}{\mathcal{O}}\)
\(\newcommand{\MKclp}{\mathcal{P}}\)
\(\newcommand{\MKclq}{\mathcal{Q}}\)
\(\newcommand{\MKclr}{\mathcal{R}}\)
\(\newcommand{\MKcls}{\mathcal{S}}\)
\(\newcommand{\MKclt}{\mathcal{T}}\)
\(\newcommand{\MKclu}{\mathcal{U}}\)
\(\newcommand{\MKclv}{\mathcal{V}}\)
\(\newcommand{\MKclw}{\mathcal{W}}\)
\(\newcommand{\MKclx}{\mathcal{X}}\)
\(\newcommand{\MKcly}{\mathcal{Y}}\)
\(\newcommand{\MKclz}{\mathcal{Z}}\)
\(\:\)גופןmathscr: ?\(\:\)
\(\newcommand{\MKsrb}{\mathscr{B}}\)
\(\newcommand{\MKsrf}{\mathscr{F}}\)
\(\:\)גופןmathfrak: אותיות גותיות לעוצמות\(\:\)
\(\newcommand{\MKfka}{\mathfrak{a}}\)
\(\newcommand{\MKfkb}{\mathfrak{b}}\)
\(\newcommand{\MKfkc}{\mathfrak{c}}\)
\(\:\)כתיבת סדרות במהירותLatexCommand ruleoffset "0.5ex"width "100col%"height "1pt"\(\:\)
\(\newcommand{\MKseq}[3]{#1_{1}#2#1_{2}#2\ldots#2#1_{#3}}\)תודה למיכאל קלי שכתב את הפקודה.
\(\newcommand{\MKseqz}[3]{#1_{0}#2#1_{1}#2\ldots#2#1_{#3}}\)תודה למיכאל קלי שכתב את הפקודה.
\(\newcommand{\MKdseq}[5]{#1_{1}#2#3_{1}#4#1_{2}#2#3_{2}#4\ldots#1_{#5}#2#3_{#5}}\)תודה למיכאל קלי שכתב את הפקודה.
\(\newcommand{\MKdseqz}[5]{#1_{0}#2#3_{0}#4#1_{1}#2#3_{1}#4\ldots#1_{#5}#2#3_{#5}}\)תודה למיכאל קלי שכתב את הפקודה.
\fbox{\thepage}\leftmark
חשבון מודולרי\fbox{\thepage}
1 התחלה
1.1 הגדרות
\(\clubsuit\)
אודי קרא לנושא הזה לזה גם "חשבון בקונגרואנציות"...
\(\clubsuit\)
כמובן שזהו יחס שקילות.
\(\clubsuit\)
הרעיון הוא ששאריות החלוקה של \(x\) ו-\(y\) ב-\(N\) שוות.
\(\clubsuit\)
\(N\) הנ"ל נקרא המודולוס.
סימון:
לכל \(x\in\MKinteger\) נסמן ב-\(\overline{x}\) את מחלקת השקילות של \(x\) ביחס הנ"ל, כלומר \(\overline{x}:=\left\{ y\in\MKinteger\mid x\equiv y\mod N\right\} \), מסמנים את קבוצת מחלקות השקילות ב-\(\MKinteger/N\MKinteger\), כאשר אנו עובדים עם יותר ממודולוס אחד נסמן את מחלקות השקילות ע"י \(\left[x\right]_{N}\).
\(\clubsuit\)
למה לסמן \(\MKinteger/N\MKinteger\) ולא פשוט \(\MKinteger/N\)? הסימון \(N\MKinteger\) הוא בעצם האידיאל \(N\cdot\MKinteger=\left\{ N\cdot a\mid a\in\MKinteger\right\} \) והסימון \(R/I\) כאשר \(R\) הוא חוג ו-\(I\) הוא אידיאל בחוג משמש לסימון לחוג המנה המושרה על \(R\) ע"י \(I\), חוג המנה הוא קבוצת מנה (כלומר קבוצת מחלקות שקילות) המושרית ע"י הגדרת מחלקת השקילות של איבר \(a\) בחוג בצורה הבאה: \(\left[a\right]:=\left\{ a+r\mid r\in I\right\} \), כלומר מבחינה אינטואיטיבית אנחנו "מאפסים" את כל איברי האידיאל (הם שקולים ל-\(0\)) וכל שני איברים בחוג שקולים זה לזה אם ההפרש ביניהם שייך לאידיאל (כלומר שאריות החלוקה שלהם1אם ניתן לבצע חילוק עם שארית בחוג. ביוצר של החוג שוות). רעיון דומה מופיע במרחבי מנה שעליהם למדנו בליניארית1: גם שם לקחנו תמ"ו \(W\) של מ"ו \(V\) והגדרנו את מחלקת השקילות של וקטור \(v\in V\) ע"י \(\left[v\right]:=\left\{ v+w\mid w\in W\right\} \) וכמו שכאן קבוצת מחלקות השקילות היא חוג שם קבוצת מחלקות השקילות היא מרחב וקטורי. מה שאני רוצה לומר בהערה הזו הוא שפעמים רבות לסימונים מתמטיים יש משמעות כללית שאינה נובעת מההקשר המסוים שבו אנו עוסקים, כך למשל הסימון \(\MKfield\left[x\right]\) לחוג הפולינומים מעל שדה הוא בסך הכל דוגמה לסימון \(A\left[x\right]\) כאשר \(A\) היא קבוצה שעליה מוגדרות פעולות חיבור וכפל ו-\(x\) הוא משתנה פורמלי המאפשר לנו לדבר על פולינום מהצורה \(ax^{2}+bx+c\) וכדומה.
\(\clubsuit\)
לכן קיימות \(N\) מחלקות שקילות שנציגיהן הם: \(0,1,2,\ldots,N-1\).
סימון:
נסמן \(\left(\MKinteger/N\MKinteger\right)^{*}:=\left\{ \overline{a}\mid\exists\overline{b}\in\MKinteger/N\MKinteger:\overline{a}\cdot\overline{b}=1\right\} \)2ה-"\(*\)" היא סימון כללי לקבוצת האיברים ההפיכים בחוג מסוים יש המסמנים אאותה ע"י "\(\times\)" במקום "\(*\)", אבל כמו שהברווז מוחתם בלידתו גם אני "נדבק" לסימונים הראשונים שאני רואה ולכן אשתמש רק ב-"\(*\)"..
\(\clubsuit\)
כאשר \(N\) ראשוני הקבוצה \(\MKinteger/N\MKinteger\) היא גם שדה (נהוג לסמנו ב-\(\MKfield_{N}\)), ראינו זאת בליניארית1.
\(\clubsuit\)
כל הטענות שאנחנו מכירים על שדות ואינן משתמשות באקסיומת ההופכי נכונות גם עבור חוג חילופי, כך למשל אם יש לאיבר הופכי אז הוא יחיד ולכן יש משמעות לסימון \(\overline{a}^{-1}\) (וכמובן גם -\(-\overline{a}\)).
\(\clubsuit\)
אם \(n\neq1\) אז \(\phi\left(n\right)=\left|\left(\MKinteger/n\MKinteger\right)^{*}\right|\).
\(\clubsuit\)
לכל \(p\in\MKnatural\) ראשוני מתקיים \(\phi\left(p\right)=p-1\).
\(\clubsuit\)
אודי קרא לנושא הזה לזה גם "חשבון בקונגרואנציות"...
יהי \(1<N\in\MKnatural\).
הגדרה 1.1. נאמר ששני מספרים \(x,y\in\MKinteger\) הם קונגרואנטיים/שקולים מודולו \(N\) אם \(N\mid\left(x-y\right)\) ואז נסמן \(x\equiv y\mod N\).
הגדרה 1.2. נאמר שקבוצה \(\left\{ r_{1},r_{2},\ldots,r_{N}\right\} \) היא מערכת נציגים שלמה אם לכל \(N\geq i,j\in\MKnatural\) כך ש-\(i\neq j\) מתקיים \(\overline{r_{i}}\neq\overline{r_{j}}\).
למה 1.3. לכל \(a,b\in\MKinteger\) ולכל \(x\in\overline{a}\) ו-\(y\in\overline{b}\) מתקיים \(\overline{a\pm b}=\overline{x\pm y}\) וגם \(\overline{a\cdot b}=\overline{x\cdot y}\).
הגדרה 1.4. נגדיר פעולות חיבור, חיסור וכפל על \(\MKinteger/N\MKinteger\): לכל \(\overline{a},\overline{b}\in\MKinteger/N\MKinteger\) נגדיר את פעולות החיבור והחיסור ע"י \(\overline{a}\pm\overline{b}:=\overline{a\pm b}\) ואת פעולת הכפל ע"י \(\overline{a}\cdot\overline{b}:=\overline{a\cdot b}\).
למה 1.5. לכל \(x\in\MKinteger\) מתקיים \(\overline{x}=\left\{ x+k\cdot N\mid k\in\MKinteger\right\} \).
למה 1.6. מהשוויון \(\overline{x}=\left\{ x+k\cdot N\mid k\in\MKinteger\right\} \) נובע גם שלכל \(a,b\in\MKinteger\), אם \(a\equiv b\mod N\) אז \(\gcd\left(a,N\right)=\gcd\left(b,N\right)\).
הגדרה 1.7. לכל \(\overline{a}\in\MKinteger/N\MKinteger\) נגדיר את המחלק המשותף המקסימלי של \(\overline{a}\) ו-\(N\) להיות \(\gcd\left(a,N\right)\) ונסמן אותו ב-\(\gcd\left(\overline{a},N\right)\).
טענה 1.8. הקבוצה \(\MKinteger/N\MKinteger\) היא חוג חילופי, כלומר היא מקיימת את כל אקסיומות השדה (ביחס לפעולות החיבור והכפל שהגדרנו) מלבד קיום הופכי לכל איבר שונה מ-\(0\), כאשר \(\overline{0}\) הוא האיבר האדיש לחיבור ו-\(\overline{1}\) הוא האיבר האדיש לכפל.
הגדרה 1.10. פונקציית אוילר תהא \(\phi:\MKnatural\rightarrow\MKnatural\) המוגדרת ע"י \(\phi\left(n\right):=\left|\left\{ n\geq m\in\MKnatural:\gcd\left(n,m\right)=1\right\} \right|\)3יש המסמנים את פונקציית אוילר ב-\(\varphi\) אך מכיוון שאודי השתמש ב-\(\phi\) גם אני אעשה זאת כאן (שוב ההחתמה). לכל \(n\in\MKnatural\), כלומר \(\phi\) מחזירה את מספר המספרים הקטנים או שווים ל-\(n\)4הנפקא מינה היחידה של הא"ש החלש היא ש-\(\phi\left(1\right)=1\). שגם זרים ל-\(n\).
מסקנה 1.11. אם \(N\) הוא ראשוני אז לכל איבר שונה מאפס יש הופכי ו-\(\MKinteger/N\MKinteger\) הוא שדה.
\(\:\)
יהי \(1<N\in\MKnatural\).
1.2 משפטים בסיסיים
למה 1.12. יהי \(f\in\MKinteger\left[x\right]\), לכל \(x,y\in\MKinteger\) המקיימים \(x\equiv y\mod N\) מתקיים\(f\left(x\right)\equiv f\left(y\right)\mod N\).
טענה 1.13. יהי \(f\in\MKinteger\left[x\right]\) אם קיים \(x\in\MKinteger\) כך ש-\(f\left(x\right)=0\) אז אותו \(x\) מקיים \(\overline{f\left(x\right)}=\overline{0}\).
\(\clubsuit\)
השימוש המרכזי של טענה זו הוא הוכחה שלפולינום נתון אין שורשים בכך שנראה שאין לו שורשים מודולו \(N\) (כאשר את \(N\) נוכל לבחור בעצמנו).
\(\clubsuit\)
למעשה ניתן להרחיב את הטענה: לכל משוואה שיש לה פתרון בשלמים יש לה גם פתרון בכל חוג שלמים מודולו \(N\), לכן אם ברצוננו להראות שלמשוואה מסוימת בשלמים אין פתרון נוכל לבחור מודולוס כאוות נפשנו (כמובן שיש לבחור אותו בצורה אסטרטגית וזה החלק הכי מסובך בעניין) ולהראות שבחוג המודולרי שלו אין פתרון למשוואה.
\(\clubsuit\)
נשים לב לכך שקיום פתרון יחיד מודולו \(\frac{N}{d}\) אומר שישנם \(d\) פתרונות מודולו \(N\).
\(\clubsuit\)
ניתן למצוא ההופכי המודולרי ע"י אלגוריתם אוקלידס המורחב: יהיו \(s,t\in\MKinteger\) מספרים זרים, האלגוריתם נותן לנו \(n,m\in\MKinteger\) כך ש-\(1=n\cdot s+m\cdot t\) ומכאן ש-\(n\cdot s\equiv1\mod t\) ו-\(m\cdot t\equiv1\mod s\), כלומר \(n\) הוא ההופכי של \(s\) מודולו \(t\) ו-\(m\) הוא ההופכי של \(t\) מודולו \(s\) (היחידות היא עד כדי שקילות מודולרית כמובן).
טענה 1.14. לכל \(x,y\in\MKinteger\) ולכל \(n\in\MKinteger\), אם \(x\equiv y\mod N\) וגם \(n\mid N\) אז \(x\equiv y\mod n\).
טענה 1.15. לכל \(x,y\in\MKinteger\) ולכל \(0\neq a\in\MKinteger\) מתקיים:\[
ax\equiv ay\mod N\Longleftrightarrow x\equiv y\mod{\frac{N}{\gcd\left(a,N\right)}}
\]
מסקנה 1.16. כלל הצמצום
מסקנה 1.17. לכל \(x,y\in\MKinteger\) ולכל \(0\neq a\in\MKinteger\) הזר ל-\(N\) מתקיים:\[
ax\equiv ay\mod N\Longleftrightarrow x\equiv y\mod N
\]
משפט 1.18. למשוואה מהצורה \(ax\equiv b\mod N\) יש פתרון אם"ם \(\gcd\left(a,N\right)\mid b\), במקרה כזה ניתן להמיר אותה (ע"פ טענה 1.4) למשוואה (נגדיר \(d:=\gcd\left(a,N\right)\)):\[
\frac{a}{d}\cdot x\equiv\frac{b}{d}\mod{\frac{N}{d}}
\]ואז \(\frac{a}{d}\) זר ל-\(\frac{N}{d}\) ולכן יש לו הופכי מודולרי והפתרונות מוכרחים לקיים:\[
x\equiv\left(\frac{a}{d}\right)^{-1}\cdot\frac{b}{d}\mod{\frac{N}{d}}
\]
טענה 1.19. הקבוצה \(\left(\MKinteger/N\MKinteger\right)^{*}\) סגורה תחת כפל, כלומר לכל \(\overline{a},\overline{b}\in\left(\MKinteger/N\MKinteger\right)^{*}\) מתקיים \(\overline{a}\cdot\overline{b}\in\left(\MKinteger/N\MKinteger\right)^{*}\).
1.3 המשפט הקטן של פרמה, פונקציית אוילר ומשפט השאריות הסיני
משפט 1.20. המשפט הקטן של פרמה יהי \(p\in\MKnatural\) מספר ראשוני, לכל \(a\in\MKinteger\) כך ש-\(a\not\equiv0\mod p\) מתקיים \(a^{p-1}\equiv1\mod p\).
הוכחה. נוכיח את המשפט הקטן של פרמה שנוכיח את משפט אוילר (משפט1.12).
מסקנה 1.21. יהי \(p\in\MKnatural\) ראשוני, לכל \(a\in\MKinteger\) כך ש-\(a\not\equiv0\mod p\) ולכל \(i,j\in\MKnatural\), מתקיים \(a^{i}\equiv a^{j}\mod N\) אם"ם \(i\equiv j\mod p-1\).
\(\clubsuit\)
המסקנה מראה לנו שמהמשפט הקטן של פרמה נובע שכדי לחשב חזקות בחשבון מודולו \(p\) ניתן לבצע חשבון מודולו \(p-1\) על המעריך.
\(\clubsuit\)
משפט אוילר הוא הכללה של המשפט הקטן של פרמה.
\(\clubsuit\)
המסקנה מראה לנו שממשפט אוילר נובע שכדי לחשב חזקות בחשבון מודולו \(N\) ניתן לבצע חשבון מודולו \(\phi\left(N\right)\) על המעריך וזאת בתנאי שהבסיס זר ל-\(N\).
\(\clubsuit\)
ממשפט השאריות הסיני נובע שכדי שנוכל לפתור קונגרואנציה כלשהי ב-\(\MKinteger/N\MKinteger\) די שנדע לפתור אותה מודולו \(p^{\MKord_{p}\left(N\right)}\) לכל \(p\) ראשוני המחלק את \(N\).
\(\clubsuit\)
כדי לקבל אינטואיציה למשפט השאריות הסיני נדמיין שני גלגלי שיניים המשתלבים זה בזה כך שמספר השיניים בגלגל אחד זר למספר השיניים בגלגל האחר, ברור לנו מבחינה אינטואיטיבית שבגלל שאין להם מחלק משותף (\(1\) לא נחשב) נוכל להגיע להשתלבות של כל שן בגלגל האחד עם כל שן בגלגל האחר5הפירמול של אינטואיציה זו הוא הידיעה שניתן להציג את \(1\) כצר"ל של שני המספרים ואם אנחנו מסוגלים לקבל את \(1\) מודולו \(n\) ע"י כפולות של \(m\) אנחנו יכולים לקבל כל שארית מודולרית מודולו \(n\) ע"י כפולות של \(m\).; עבור מספר גדול יותר של גלגלי שיניים נשתמש באינדוקציה. כמובן שאפשר ממש לפרמל את האינטואיציה הזו לכדי הוכחה מתמטית, ראו את ה של המשפט.
\(\clubsuit\)
ניתן היה גם להוכיח ש-\(f\) על ולכן מהשוויון בין הגדלים של התחום והטווח נובע שהיא חח"ע, ראו הדגמה לכך בהוכחה הראשונה של טענה1.17.
\(\clubsuit\)
אני רוצה להביא כאן המחשה קטנה לחשיבות האינטואיטיבית של העובדה שעבור מספרים זרים ניתן להציג את \(1\) כצר"ל שלהם:\[\begin{align*}
x & \equiv{\color{red}1}\mod 3\\
x & \equiv{\color{blue}2}\mod 5\\
x & \equiv{\color{green}2}\mod 7
\end{align*}\]אמנם ניתן לפתור זאת ע"פ ההוכחה השנייה שלמדנו אולם ישנה דרך דומה אבל קצרה הרבה יותר כשמדובר במספרים קטנים:\[\begin{align*}
& 3\cdot2\equiv{\color{violet}6}\equiv1\mod 5\\
& {\color{blue}2}-{\color{red}1}=1\equiv1\mod 5\\
\Rightarrow & {\color{orange}7}={\color{violet}6}\cdot\left({\color{blue}2}-{\color{red}1}\right)+{\color{red}1}\equiv0+1\equiv{\color{red}1}\equiv x\mod 3\\
\Rightarrow & {\color{orange}7}={\color{violet}6}\cdot\left({\color{blue}2}-{\color{red}1}\right)+{\color{red}1}\equiv1+1\equiv{\color{blue}2}\equiv x\mod 5\\
& \left(3\cdot5\right)\equiv{\color{purple}15}\equiv1\mod 7\\
& {\color{orange}7}\equiv0\mod 7\\
\Rightarrow & {\color{green}2}-{\color{orange}7}\equiv{\color{green}2}\mod 7\\
\Rightarrow & 37={\color{purple}15}\cdot{\color{green}2}+{\color{orange}7}\equiv{\color{purple}15}\cdot\left({\color{green}2}-{\color{orange}7}\right)+{\color{orange}7}\equiv{\color{orange}7}\equiv{\color{violet}6}\cdot\left({\color{blue}2}-{\color{red}1}\right)+{\color{red}1}\equiv{\color{red}1}\equiv x\mod 3\\
\Rightarrow & 37={\color{purple}15}\cdot{\color{green}2}+{\color{orange}7}\equiv{\color{purple}15}\cdot\left({\color{green}2}-{\color{orange}7}\right)+{\color{orange}7}\equiv{\color{orange}7}\equiv{\color{violet}6}\cdot\left({\color{blue}2}-{\color{red}1}\right)+{\color{red}1}\equiv{\color{blue}2}\equiv x\mod 5\\
\Rightarrow & 37={\color{purple}15}\cdot{\color{green}2}+{\color{orange}7}\equiv{\color{purple}15}\cdot\left({\color{green}2}-{\color{orange}7}\right)+{\color{orange}7}\equiv{\color{green}2}\equiv x\mod 7
\end{align*}\]כלומר אני מסובב את גלגל השעון של \(3\) כדי לקבל \(1\) בשעון של \(5\) (קיבלנו \(6\)), כעת אני בודק כמה אני צריך להוסיף ל-\({\color{red}1}\) כדי לקבל את \({\color{blue}2}\) (בשעון של \(5\)) ומוסיף ל-\({\color{red}1}\) (בשעון של \(5\)) את \(6\) כפול ההפרש (קיבלנו \({\color{orange}7}\)); לאחר מכן אני מסובב את גלגל השעון של \(3\cdot5\) כדי לקבל \(1\) בשעון של \(7\) (קיבלנו \(15\)), כעת אני בודק כמה אני צריך להוסיף ל-\({\color{orange}7}\) כדי לקבל את \({\color{green}2}\) (בשעון של \(7\)) ומוסיף ל-\({\color{orange}7}\) (בשעון של \(7\) שזה \(0\)!) את \({\color{purple}15}\) כפול ההפרש6ניתן היה גם להתייחס ל-\({\color{green}2}-{\color{orange}7}\) כ-\(-5\) ואז היינו מקבלים \(-68={\color{purple}15}\cdot\left(-5\right)+{\color{orange}7}\equiv37\mod 105\) (והרי \(105=3\cdot5\cdot7\)).. בכל שלב מובטח שהכול יהיה תקין מפני שאני מוסיף כפולות של כל המספרים שכבר עברתי, כך שאצלם אני לא משנה דבר, ובמספר שאני עובד עליו עכשיו אני מוסיף אחדות ולכן אוכל להגיע לאן שארצה.
\(\clubsuit\)
כדי להוכיח את נכונות המסקנה נשים לב לכך שדי להראות שהיא נכונה עבור חזקות של ראשוני כלשהו ואז מהכפליות של הפונקציה עבור מספרים זרים נקבל את הטענה עבור כל מספר, דרך זו תקפה לכל פונקציה כפלית עבור מספרים זרים.
מסקנה 1.22. יהי \(p\in\MKnatural\) מספר ראשוני, לכל \(a\in\MKinteger\) מתקיים \(a^{p}\equiv a\mod p\).
למה 1.23. יהי \(a\in\MKinteger\) זר ל-\(N\) ויהיו \(r_{1},r_{2},\ldots,r_{\phi\left(N\right)}\in\MKinteger\) כך ש-\(\left\{ \overline{r_{1}},\overline{r_{2}},\ldots,\overline{r_{\phi\left(N\right)}}\right\} =\left(\MKinteger/N\MKinteger\right)^{*}\), מתקיים \(\left\{ \overline{a\cdot r_{1}},\overline{a\cdot r_{2}},\ldots,\overline{a\cdot r_{\phi\left(N\right)}}\right\} =\left(\MKinteger/N\MKinteger\right)^{*}\).
משפט 1.24. משפט אוילר לכל \(a\in\MKinteger\) כך ש-\(a\) זר ל-\(N\) מתקיים \(a^{\phi\left(N\right)}\equiv1\mod N\).
הוכחה. נשתמש בסימונים של הלמה האחרונה ונשים לב לכך שנובע ממנה כי:\[
a^{\phi\left(N\right)}\cdot\prod_{i=1}^{\phi\left(N\right)}r_{i}=\prod_{i=1}^{\phi\left(N\right)}\left(a\cdot r_{i}\right)\equiv\prod_{i=1}^{\phi\left(N\right)}r_{i}\mod N
\]כעת נזכר שכל האיברים במכפלה שבאגף ימין הפיכים ולכן גם המכפלה עצמה הפיכה וניתן לצמצם בה את שני האגפים, כלומר \(a^{\phi\left(N\right)}\equiv1\mod N\) כנדרש.
מסקנה 1.25. לכל \(a\in\MKinteger\) זר ל-\(N\) ולכל \(i,j\in\MKnatural\), מתקיים \(a^{i}\equiv a^{j}\mod N\) אם"ם \(i\equiv j\mod{\phi}\left(N\right)\).
משפט 1.26. משפט השאריות הסיני (CRT - Chinese Remainder Theorem) יהיו \(1<m_{1},m_{2},\ldots,m_{k}\in\MKnatural\) זרים זה לזה בזוגות ונסמן \(\begin{alignedat}{1}m:=\begin{alignedat}{1}\prod_{i=1}^{k}m_{i}\end{alignedat}
\end{alignedat}
\), לכל \(a_{1},a_{2},\ldots,a_{k}\in\MKinteger\) קיים \(m>x\in\MKnatural_{0}\) יחיד המקיים7כלומר קיים פתרון יחיד מודולו \(m\), או אם תרצו: כל שני פתרונות שקולים מודולו \(m\).:\[\begin{align*}
x & \equiv a_{1}\mod m_{1}\\
x & \equiv a_{2}\mod m_{2}\\
& \vdots\\
x & \equiv a_{k}\mod m_{k}
\end{align*}\]
נביא שלוש הוכחות שהן בעצם שתיים.
הוכחה. הוכחה1- לא קונסטרוקטיבית יהיו \(1<m_{1},m_{2},\ldots,m_{k}\in\MKnatural\) זרים זה לזה בזוגות ונסמן \(\begin{alignedat}{1}m:=\begin{alignedat}{1}\prod_{i=1}^{k}m_{i}\end{alignedat}
\end{alignedat}
\). תהא \(f:\MKinteger/m\MKinteger\rightarrow\MKinteger/m_{1}\MKinteger\times\MKinteger/m_{2}\MKinteger\times\ldots\times\MKinteger/m_{k}\MKinteger\) המוגדרת ע"י (לכל \(\left[x\right]_{m}\in\MKinteger/m\MKinteger\)):\[
f\left(\left[x\right]_{m}\right):=\left(\left[x\right]_{m_{1}},\left[x\right]_{m_{2}},\ldots,\left[x\right]_{m_{k}}\right)
\]מטענה1.3נובע ש-\(f\) אינה תלויה בבחירת הנציג ולכן מוגדרת היטב. נוכיח ש-\(f\) חח"ע ומכאן שהיא גם על שהרי התחום והטווח שלה הן קבוצות סופיות שגודלן זהה. יהיו \(x,y\in\MKinteger\) כך ש-\(x\equiv y\mod m_{i}\) לכל \(k\geq i\in\MKnatural\), א"כ מתקיים \(m_{i}\mid x-y\) לכל \(k\geq i\in\MKnatural\) ומכאן שגם \(\MKlcm\left(m_{1},m_{2},\ldots,m_{k}\right)\mid x-y\). כעת נשים לב לכך שמכיוון ש-\(m_{1},m_{2},\ldots,m_{k}\) זרים זה לזה מתקיים בהכרח:\[
\MKlcm\left(m_{1},m_{2},\ldots,m_{r}\right)=\prod_{i=1}^{k}m_{i}=m
\]ומכאן ש-\(x\equiv y\mod m\) ומהגדרה \(f\) חח"ע. התחום והטווח של \(f\) הן קבוצות סופיות בגודל זהה ולכן עובדת היותה של \(f\) חח"ע אומרת ש-\(f\) גם על ולכן הפיכה, כלומר לכל \(\left(a_{1},a_{2},\ldots,a_{k}\right)\in\MKinteger/m_{1}\MKinteger\times\MKinteger/m_{2}\MKinteger\times\ldots\times\MKinteger/m_{k}\MKinteger\) קיימת \(x\in\MKinteger/m\MKinteger\) יחידה כך שמתקיים:\[
f\left(x\right)=\left(a_{1},a_{2},\ldots,a_{k}\right)
\]ומכאן שלכל \(a_{1},a_{2},\ldots,a_{k}\in\MKinteger\) קיים \(m>x\in\MKnatural_{0}\) יחיד כך שמתקיים:\[\begin{align*}
x & \equiv a_{1}\mod m_{1}\\
x & \equiv a_{2}\mod m_{2}\\
& \vdots\\
x & \equiv a_{k}\mod m_{k}
\end{align*}\]
הוכחה. הוכחה2- קונסטרוקטיבית יהיו \(1<m_{1},m_{2},\ldots,m_{k}\in\MKnatural\) זרים זה לזה בזוגות ונסמן \(\begin{alignedat}{1}m:=\begin{alignedat}{1}\prod_{i=1}^{k}m_{i}\end{alignedat}
\end{alignedat}
\). לכל \(k\geq i\in\MKnatural\) נסמן \(n_{i}:=\frac{m}{m_{i}}\), א"כ \(\gcd\left(n_{i},m_{i}\right)=1\) לכל \(k\geq i\in\MKnatural\) ולכן לכל \(k\geq i\in\MKnatural\) קיימים \(r_{i},s_{i}\in\MKinteger\) כך ש-\(r_{i}\cdot m_{i}+s_{i}\cdot n_{i}=1\). א"כ יהיו \(r_{i},s_{i}\) כנ"ל ונסמן \(x_{i}:=s_{i}\cdot n_{i}\) (כל זה לכל \(k\geq i\in\MKnatural\) בנפרד), כעת נשים לב לכך שלכל \(k\geq i,j\in\MKnatural\) מתקיים \(x_{i}\equiv\delta_{ij}\mod m_{j}\)8\(\delta_{ij}\) (הדלתא של קרונקר) מוגדרת ע"י:\[
\delta_{ij}:=\begin{cases}
1 & i=j\\
0 & i\neq j
\end{cases}
\] ולכן אם נסמן:\[
x:=\sum_{i=1}^{k}a_{i}\cdot x_{i}
\]נקבל שמתקיים \(x\equiv a_{i}\mod m_{i}\) לכל \(k\geq i\in\MKnatural\). כפי שראינו בהוכחה הקודמת לכל \(y\in\MKinteger\) כך ש-\(x\equiv y\mod m\) מתקיים גם כן \(y\equiv a_{i}\mod m_{i}\) ולכן בהכרח קיים \(m>x\in\MKnatural_{0}\) המקיים זאת, היחידות נובעת מעקרון שובך היונים.
הוכחה. הוכחה3- הוכחה2רק באינדוקציה נוכיח את המשפט באינדוקציה על \(k\), עבור \(k=1\) המשפט טריוויאלי ולכן נעבור לצעד האינדוקציה. יהי \(k\in\MKnatural\), יהיו \(1<m_{1},m_{2},\ldots,m_{k}\in\MKnatural\) זרים זה לזה בזוגות ו-\(a_{1},a_{2},\ldots,a_{k}\in\MKinteger\); נניח שקיים \(x\in\MKinteger\) כך שמתקיים (הנחת האינדוקציה):\[\begin{align*}
x & \equiv a_{1}\mod m_{1}\\
x & \equiv a_{2}\mod m_{2}\\
& \vdots\\
x & \equiv a_{k}\mod m_{k}
\end{align*}\]ויהי \(x\) כנ"ל. יהי \(1<m_{k+1}\in\MKnatural\) כך ש-\(\gcd\left(m_{k+1},m_{i}\right)=1\) לכל \(k\geq i\in\MKnatural\) ויהא \(a_{k+1}\in\MKinteger\). נסמן \(\begin{alignedat}{1}m:=\begin{alignedat}{1}\prod_{i=1}^{k}m_{i}\end{alignedat}
\end{alignedat}
\), מהגדרה מתקיים \(\gcd\left(m_{k+1},m\right)=1\) ולכן קיימים \(r,s\in\MKinteger\) כך ש-\(r\cdot m_{k+1}+s\cdot m=1\), יהיו \(r,s\) כנ"ל.\[\begin{align*}
& \Rightarrow a_{k+1}-x=\left(a_{k+1}-x\right)\cdot r\cdot m_{k+1}+\left(a_{k+1}-x\right)\cdot s\cdot m\\
& \Rightarrow a_{k+1}-x\equiv\left(a_{k+1}-x\right)\cdot s\cdot m\mod m_{k+1}\\
& \Rightarrow a_{k+1}\equiv x+\left(a_{k+1}-x\right)\cdot s\cdot m\mod m_{k+1}
\end{align*}\]כמובן שמתקיים \(x+\left(a_{k+1}-x\right)\cdot s\cdot m\equiv x\mod m\) ולכן \(x+\left(a_{k+1}-x\right)\cdot s\cdot m\equiv a_{i}\mod m_{i}\) לכל \(k\geq i\in\MKnatural\). א"כ הוכחנו את הקיום של הפתרון, היחידות נובעת כרגיל מעקרון שובך היונים.
מסקנה 1.27. יהיו \(1<m_{1},m_{2},\ldots,m_{r}\in\MKnatural\) זרים זה לזה בזוגות, יהיו \(f_{1},f_{2},\ldots,f_{r}\in\MKinteger\left[x\right]\) ויהיו \(a_{1},a_{2},\ldots,a_{r}\in\MKinteger\) כך ש-\(f\left(a_{i}\right)\equiv0\mod m_{i}\) לכל \(r\geq i\in\MKnatural\); קיים \(n\in\MKinteger\) כך ש-\(f\left(n\right)\equiv0\mod m_{i}\) לכל \(r\geq i\in\MKnatural\).
טענה 1.28. יהי \(p\in\MKnatural\) מספר ראשוני, לכל \(s\in\MKnatural\) מתקיים:\[
\phi\left(p^{s}\right)=p^{s}-p^{s-1}=p^{s-1}\cdot\left(p-1\right)=p^{s}\cdot\left(1-\frac{1}{p}\right)
\]
טענה 1.29. פונקציית אוילר כפלית עבור מספרים זרים9בהמשך, כשנלמד על פונקציות אריתמטיות, נקרא לפונקציה אריתמטית כזו כפלית סתם למרות שזו אינה ההגדרה הרגילה של פונקציה כפלית., כלומר לכל \(n,m\in\MKnatural\) הזרים זה לזה מתקיים \(\phi\left(n\cdot m\right)=\phi\left(n\right)\cdot\phi\left(m\right)\).
הוכחה. הוכחה1- באמצעות הפונקציה שבהוכחה הראשונה של משפט השאריות הסיני יהיו \(n,m\in\MKnatural\) מספרים זרים זה לזה ותהא \(f:\left(\MKinteger/nm\MKinteger\right)^{*}\rightarrow\left(\MKinteger/n\MKinteger\right)^{*}\times\left(\MKinteger/m\MKinteger\right)^{*}\) פונקציה המוגדרת ע"י (לכל \(\left[x\right]_{nm}\in\MKinteger/nm\MKinteger\))10הפונקציה מוגדרת היטב מפני שכל מספר זר ל-\(nm\) זר גם ל-\(n\) ו-\(m\) בנפרד.:\[
f\left(\left[x\right]_{nm}\right):=\left(\left[x\right]_{n},\left[x\right]_{m}\right)
\]ראינו ב של משפט השאריות הסיני שזוהי פונקציה חח"ע11\(f\) בהוכחה שלנו היא צמצום של \(f\) בהוכחה הנ"ל לתת-הקבוצה \(\left(\MKinteger/nm\MKinteger\right)^{*}\subseteq\MKinteger/nm\MKinteger\) ולכן היא "יורשת" את תכונת החד-חד-ערכיות., מצד שני זוהי גם פונקציה על מפני שלכל \(\left(a,b\right)\in\left(\MKinteger/n\MKinteger\right)^{*}\times\left(\MKinteger/m\MKinteger\right)^{*}\) מתקיים:\[
f\left(bx\cdot n+ay\cdot m\right)=\left(ay\cdot m,bx\cdot n\right)=\left(a,b\right)
\]כאשר \(x,y\) הם שלמים המקיימים \(1=x\cdot n+y\cdot m\) ולכן גם \(x\cdot n\equiv1\mod m\) ו-\(y\cdot m\equiv1\mod n\). מכאן שהתחום והטווח של \(f\) הן קבוצות באותו הגודל (שתיהן סופיות) וממילא:\[\begin{align*}
\phi\left(n\cdot m\right) & =\left|\left(\MKinteger/nm\MKinteger\right)^{*}\right|=\left|\left(\MKinteger/n\MKinteger\right)^{*}\times\left(\MKinteger/m\MKinteger\right)^{*}\right|\\
& =\left|\left(\MKinteger/n\MKinteger\right)^{*}\right|\cdot\left|\left(\MKinteger/m\MKinteger\right)^{*}\right|=\phi\left(n\right)\cdot\phi\left(m\right)
\end{align*}\]
הוכחה. הוכחה2 - הכלה והדחה נוכיח את הטענה עבור מכפלת חזקות של שני ראשוניים שונים ואז מאינדוקציה תנבע המסקנה כולה. יהיו \(p,q\in\MKnatural\) שני ראשוניים שונים, מעיקרון ההכלה וההדחה12\(p^{s-1}\cdot q^{t}\) הוא מספר הכפולות של \(p\) הקטנות או שוות ל-\(p^{s}\cdot q^{t}\), כמו כן \(q^{t-1}\cdot p^{s}\) הוא מספר הכפולות של \(q\) בטווח זה ואילו \(p^{s-1}\cdot q^{t-1}\) הוא כמות המספרים שהם כפולות של שניהם שהרי \(p\) ו-\(q\) זרים זה לזה ולכן כל כפולה של שניהם היא כפולה של \(p\cdot q\). נובע שלכל \(s,t\in\MKnatural\) מתקיים:\[
\phi\left(p^{s}\cdot q^{t}\right)=p^{s}\cdot q^{t}-p^{s-1}\cdot q^{t}-q^{t-1}\cdot p^{s}+p^{s-1}\cdot q^{t-1}
\]\[\begin{align*}
\Rightarrow\phi\left(p^{s}\cdot q^{t}\right) & =p^{s-1}\cdot q^{t-1}\cdot\left(p\cdot q-q-p+1\right)\\
& =p^{s-1}\cdot q^{t-1}\cdot\left(p-1\right)\cdot\left(q-1\right)\\
& =p^{s-1}\cdot\left(p-1\right)\cdot q^{t-1}\cdot\left(q-1\right)\\
& =\phi\left(p^{s}\right)\cdot\phi\left(q^{t}\right)
\end{align*}\]כעת נקבל מאינדוקציה שהטענה נכונה לכל מספר של ראשוניים שונים ומהקיבוץ של הכפל נקבל את הטענה עבור מספרים זרים באשר הם13ראינו שניתן להציג כל מספר שלם כמכפלת חזקות של ראשוניים, וכמדובר בשני מספרים זרים הם אינם חולקים ראשוני משותף בפירוק..
מסקנה 1.30. יהי \(n\in\MKnatural\) ויהיו \(p_{1},p_{2},\ldots,p_{r}\in\MKnatural\) כל הראשוניים המחלקים את \(n\) ללא חזרות14כלומר לכל \(r\geq i,j\in\MKnatural\) מתקיים \(i=j\Longleftrightarrow p_{i}=p_{j}\)., מתקיים:\[
\phi\left(n\right)=\prod_{i=1}^{r}\left(\left(p_{i}\right)^{\MKord_{p_{i}}\left(n\right)-1}\right)\cdot\prod_{i=1}^{r}\left(p_{i}-1\right)=n\cdot\prod_{i=1}^{r}\left(1-\frac{1}{p_{i}}\right)
\]
מסקנה 1.31. יהי \(n\in\MKnatural\), קיים \(k\in\MKnatural_{0}\) כך ש-\(\phi\left(n\right)=2^{k}\) אם"ם כל הראשוניים האי-זוגיים בפירוק של \(n\) הם ראשוני פרמה והריבוי שלהם הוא \(1\).
1.4 משפטים נוספים
משפט 1.32. משפט וילסון(Wilson)15ערך בוויקיפדיה האנגלית: John Wilson. יהי \(p\in\MKnatural\) מספר ראשוני, מתקיים:\[
\left(p-1\right)!\equiv-1\mod p
\]עבור \(p=2\) המשפט טריוויאלי, נראה כעת שתי הוכחות עבור \(p\neq2\).
הוכחה. הוכחה1- שימוש בתכונות השדה \(\MKinteger/p\MKinteger\) הוא שדה ולכן מחלקות השקילות היחידות שהן ההופכיות של עצמן הן \(\overline{1}\) ו-\(\overline{-1}=\overline{p-1}\)16הוכחה: יהי \(p>a\in\MKnatural\) ונניח ש-\(a^{2}\equiv1\mod p\), מכאן שמתקיים \(\left(a+1\right)\left(a-1\right)\equiv a^{2}-1\equiv0\mod p\) ולכן בהכרח מתקיים \(a\equiv1\mod p\) ו/או ש-\(a\equiv-1\mod p\)., א"כ לכל \(i\in\MKnatural\) כך ש-\(1<i<p-1\) קיים \(i\neq j\in\MKnatural\) כך ש-\(1<j<p-1\) ובנוסף \(i\cdot j\equiv1\mod p\).\[\begin{align*}
\Rightarrow\left(p-1\right)! & \equiv\left(p-1\right)\cdot1\mod p\\
\Rightarrow\left(p-1\right)! & \equiv p-1\equiv-1\mod p
\end{align*}\]
הוכחה. הוכחה2- שימוש בפירוק של פולינומים נתבונן בפולינום \(f\left(x\right):=x^{p-1}-1\) מעל ל-\(\MKinteger/p\MKinteger\), מהמשפט הקטן של פרמה נובע שלכל \(p>x\in\MKnatural\) מתקיים \(x^{p-1}-1\equiv0\mod p\), כלומר ל-\(f\) יש \(p-1\) שורשים שונים ומכיוון שגם דרגתו היא \(p-1\) הרי שהוא מתפרק למכפלת גורמים ליניאריים שונים:\[
f\left(x\right)=x^{p-1}-1=\prod_{i=1}^{p-1}\left(x-i\right)
\]ומכאן שמתקיים17המקדם החופשי של פולינום המתפרק לגורמים ליניאריים הוא מכפלת הנגדיים של השורשים.:\[
\left(p-1\right)!\equiv\prod_{i=1}^{p-1}i\equiv\left(-1\right)^{p-1}\cdot\prod_{i=1}^{p-1}\left(-i\right)\equiv-1\mod p
\]
טענה 1.33. יהי \(1<n\in\MKnatural\), \(n\) הוא מספר ראשוני אם"ם \(\left(n-1\right)!\equiv-1\mod n\).
הוכחה. נוכיח את הכיוון ההפוך למשפט וילסון: נניח ש-\(\left(n-1\right)!\equiv-1\mod n\) ונניח בשלילה ש-\(n\) אינו ראשוני. מכאן שקיים \(a\in\MKnatural\) כך ש-\(1<a<n\) ו-\(a\mid n\), מהגדרה אותו \(a\) מקיים \(a\mid\left(n-1\right)!\) בסתירה לכך שע"פ טענה1.3 מתקיים \(\left(n-1\right)!\equiv-1\mod a\), מכאן שהנחת השלילה אינה נכונה ו-\(n\) ראשוני.
משפט 1.34. יהי \(2<p\in\MKnatural\) מספר ראשוני, קיים \(x\in\MKinteger\) כך ש-\(x^{2}\equiv-1\mod p\) אם"ם \(p\equiv1\mod 4\).
הוכחה. \(\:\)
\(\Leftarrow\) נניח שקיים \(x\in\MKinteger\) כך ש-\(x^{2}\equiv-1\mod p\) ויהי \(x\) כנ"ל. מהמשפט הקטן של פרמה נובע שמתקיים:\[
1\equiv x^{p-1}\equiv\left(x^{2}\right)^{\frac{p-1}{2}}\equiv\left(-1\right)^{\frac{p-1}{2}}\mod p
\]אבל:\[
\left(-1\right)^{\frac{p-1}{2}}=\begin{cases}
1 & \frac{p-1}{2}\in\MKeven\\
-1 & \frac{p-1}{2}\in\MKodd
\end{cases}=\begin{cases}
1 & p\equiv1\mod 4\\
-1 & p\equiv3\mod 4
\end{cases}
\]ומכיוון ש-\(p\neq2\) נדע ש-\(1\not\equiv-1\mod p\) ולכן בהכרח מתקיים \(p\equiv1\mod 4\).
\(\Rightarrow\) נניח ש-\(p\equiv1\mod 4\) ומכאן ש-\(p-1\equiv0\mod 4\) וממילא \(\frac{p-1}{2}\equiv0\mod 2\), כלומר \(\frac{p-1}{2}\in\MKeven\) ו-\(\left(-1\right)^{\frac{p-1}{2}}=1\). ממשפט וילסון נובע שמתקיים:\[\begin{align*}
-1 & \equiv\left(p-1\right)!\equiv\prod_{i=1}^{p-1}i\equiv\left(\prod_{i=\frac{p-1}{2}+1}^{p-1}i\right)\cdot\left(\prod_{i=1}^{\frac{p-1}{2}}i\right)\equiv\left(\prod_{i=1}^{\frac{p-1}{2}}-i\right)\cdot\left(\prod_{i=1}^{\frac{p-1}{2}}i\right)\\
& \equiv\left(-1\right)^{\frac{p-1}{2}}\cdot\left(\prod_{i=1}^{\frac{p-1}{2}}i\right)\cdot\left(\prod_{i=1}^{\frac{p-1}{2}}i\right)\equiv\left(\prod_{i=1}^{\frac{p-1}{2}}i\right)^{2}\mod p
\end{align*}\]כלומר קיים \(x\in\MKinteger\) כך ש-\(x^{2}\equiv-1\mod p\).
טענה 1.35. קיימים אינסוף ראשוניים השקולים ל-\(1\) מודולו \(4\), כלומר הקבוצה \(\left\{ p\in\MKprime\mid p\equiv1\mod 4\right\} \) היא קבוצה אינסופית.
הוכחה. נניח בשלילה מספר הראשוניים השקולים ל-\(1\) מודולו \(4\) הוא סופי ויהיו \(p_{1},p_{2},\ldots,p_{r}\in\MKnatural\) כל הראשוניים הללו, נסמן:\[
m:=\prod_{i=1}^{r}\left(p_{i}\right)^{2},\ n:=4m+1
\]יהי \(p\in\MKnatural\) ראשוני המחלק את \(n\), מהגדרה מתקיים \(4m\equiv-1\mod p\); נשים לב לכך שמתקיים:\[
4m=\left(2\cdot\prod_{i=1}^{r}p_{i}\right)^{2}
\]ולכן קיים \(x\in\MKinteger\) כך ש-\(x^{2}\equiv-1\mod p\) ומכאן שע"פ המשפט האחרון מתקיים \(p\equiv1\mod 4\). אבל מהגדרה \(p\) אינו אחד מן הראשוניים הנ"ל (שהרי \(p_{i}\) אינו מחלק את \(n\) לכל \(r\geq i\in\MKnatural\)) וזאת בסתירה לכך שאלו כל הראשוניים השקולים ל-\(1\) מודולו\(4\), מכאן שהנחת השלילה אינה נכונה וקיימים אינסוף ראשוניים השקולים ל-\(1\) מודולו \(4\).
טענה 1.36. קיימים אינסוף ראשוניים השקולים ל-\(3\) מודולו \(4\), כלומר הקבוצה \(\left\{ p\in\MKprime\mid p\equiv3\mod 4\right\} \) היא קבוצה אינסופית.
הוכחה. נניח בשלילה מספר הראשוניים השקולים ל-\(1\) מודולו \(4\) הוא סופי ויהיו \(p_{1},p_{2},\ldots,p_{r}\in\MKnatural\) כל הראשוניים הללו, נסמן:\[
m:=\prod_{i=1}^{r}p_{i},\ n:=4m-1
\]נשים לב לכך ש-\(n\equiv3\mod 4\) ולכן בהכרח קיים ראשוני השקול ל-\(3\) מודולו \(4\) המחלק את \(n\), שהרי \(n\) אי-זוגי ומכפלה של ראשוניים השקולה ל-\(1\) מודולו \(4\) תהיה גם היא שקולה ל-\(1\) מודולו \(4\). א"כ יהי \(p\in\MKnatural\) ראשוני המחלק \(n\) כך ש-\(p\equiv3\mod 4\), מהגדרה \(p\) אינו אחד מן הראשוניים הנ"ל (שהרי \(p_{i}\) אינו מחלק את \(n\) לכל \(r\geq i\in\MKnatural\)) וזאת בסתירה לכך שאלו כל הראשוניים השקולים ל-\(3\) מודולו\(4\), מכאן שהנחת השלילה אינה נכונה וקיימים אינסוף ראשוניים השקולים ל-\(3\) מודולו \(4\).
\(\clubsuit\)
הטענות בעצם אומרות שבסדרות \(\left(4n+1\right)_{n=0}^{\infty}\) ו-\(\left(4n+3\right)_{n=0}^{\infty}\) יש אינסוף ראשוניים ובכך הן מקרה פרטי של משפט דיריכלה שראינו בנושא הקודם: לכל \(a,d\in\MKnatural\) הזרים זה לזה קיימים אינסוף איברים ראשונים שהם איברים בסדרה החשבונית \(\left(a+dn\right)_{n=0}^{\infty}\).
\(\clubsuit\)
נזכיר שכדי לפתור מערכות משוואות ליניאריות (ממ"ל) מעל שדה ראינו בליניארית1 את אלגוריתם הדירוג (דירוג מטריצות) המשתמש בשלוש פעולות שורה אלמנטריות (פש"א): החלפת שורות, כפל שורה בסקלר מהשדה והוספת כפולה של שורה אחת לשורה אחרת; כשמבצעים את האלגוריתם מעל חוג שלמים מודולרי \(\MKinteger/N\MKinteger\) יש להיזהר בשתי הפעולות האחרונות: לא לכל סקלר בחוג יש הופכי, זה הורס את האלגוריתם וכבר א"א לבצעו בצורה מכנית18אולי ניתן לתקן אותו אך כפי שלמדנו אותו הוא כבר לא עובד משום שהוא השתמש בכפל בהופכי ע"מ לייצר אחדות מובילים. ויש לחשוב במהלך הדירוג.
\(\clubsuit\)
ההוכחה של המשפט משתמשת בכלל קרמר ובלמה שקדמה לו (ראו בקובץ "פונקציות נפח - טענות בלבד"), זוכרים שחשבנו שהוא מיותר לחלוטין מפני שאלגוריתם הדירוג הרבה יותר יעיל? אז הנה שימוש שלו.
\(\clubsuit\)
נשים לב לכך שמדובר בנוסחת השורשים שהרי \(d\) הוא \(\sqrt{b^{2}-4ac}\) ואז \(\left(-b+d\right)\cdot\left(2a\right)^{-1}\) הוא בעצם:\[
\frac{-b+\sqrt{b^{2}-4ac}}{2a}
\]שימו לב שההערה הזו ממש לא פורמלית, הביטוי \(\sqrt{b^{2}-4ac}\) אינו מוגדר שהרי ייתכן שלשארית ריבועית יש יותר משורש אחד.
\(\clubsuit\)
הדמיון לנוסחת השורשים אינו מקרי כמובן, ההוכחה של נוסחת השורשים תעבוד גם כאן אלא שעלינו לשים לב לכך שאנו מוציאים שורש של \(b^{2}-4ac\) ומחלקים ב-\(2a\), כלומר הפעולות הללו צריכות להיות מוגדרות כדי שיהיה פתרון ומכאן נובעים התנאים הנ"ל.
\(\clubsuit\)
הלמה של הנזל, יחד עם משפט השאריות הסיני, נותנים לנו דרך מצוא שורשים של פולינומים בכל מודולוס ובתנאי שאנחנו יודעים את השורשים של הפולינום עבור כל אחד מהראשוניים המופיעים בפירוק של המודולוס.
\(\clubsuit\)
בוויקיפדיה מופיעה הרחבה ללמה של הנזל העוסקת במקרה שבו \(f'\left(a\right)\equiv0\mod p\):
אם \(f'\left(a\right)\equiv0\mod p\) וגם \(f\left(a\right)\equiv0\mod p^{e+1}\) אז \(f\left(a+t\cdot p^{e}\right)\equiv0\mod p^{e+1}\) לכל \(t\in\MKinteger\).
אם \(f'\left(a\right)\equiv0\mod p\) וגם \(f\left(a\right)\not\equiv0\mod p^{e+1}\) אז לא קיים \(t\in\MKinteger\) כך ש-\(f\left(a+t\cdot p^{e}\right)\equiv0\mod p^{e+1}\), כלומר אין ל-\(f\) שורשים מודולו \(p^{e+1}\).
\(\clubsuit\)
\(a\) כנ"ל נקרא "שורש פשוט" של הפולינום, כלומר שורש פשוט הוא מספר שהצבתו בפולינום נותנת \(0\) אבל הצבתו בפולינום הנגזרת שונה מ-\(0\).
משפט 1.37. יהיו \(A\in M_{n}\left(\MKinteger/N\MKinteger\right)\) ו-\(b\in\left(\MKinteger/N\MKinteger\right)^{n}\), למערכת המשוואות הליניאריות \(A\cdot x\equiv b\mod N\)19הכוונה היא שהווקטורים בשני האגפים מחושבים מעל \(\MKinteger\) ומתקיימת שקילות מודולו \(N\) בכל קואורדינטה. יש פתרון יחיד אם"ם \(\overline{\det A}\in\left(\MKinteger/N\MKinteger\right)^{*}\), כלומר אם"ם הדטרמיננטה של \(A\) היא מספר זר ל-\(N\), אחרת ייתכן שאין פתרונות כלל או שיש יותר מפתרון אחד.
הוכחה. בליניארית1ראינו את הלמה הבאה:
למה. תהא \(M\in M_{n}\left(\MKfield\right)\) מטריצה (\(\MKfield\) הוא שדה), יהי \(v\in\MKfield^{n}\) ונסמן ב-\(M^{\left(i\right)}\) את המטריצה המתקבלת מ-\(M\) ע"י החלפת העמודה ה-\(i\) ב-\(v\) (לכל \(n\geq i\in\MKnatural\)). אם קיים \(x\in\MKfield^{n}\) כך ש-\(M\cdot x=v\) אז עבור אותו \(x\) מתקיים (לכל \(n\geq i\in\MKnatural\)):\[
\det M^{\left(i\right)}=\left(\det M\right)\cdot x_{i}
\]
למה. נניח שקיים \(x\in\MKinteger^{n}\) כך ש-\(A\cdot x\equiv b\mod N\) ויהי \(x\) כנ"ל. נסתכל על \(A\) כמטריצה ב-\(M_{n}\left(\MKrational\right)\), א"כ גם \(A\) מקיימת \(\det A^{\left(i\right)}=\left(\det A\right)\cdot x_{i}\) (לכל \(n\geq i\in\MKnatural\))20נסמן ב-\(A^{\left(i\right)}\) את המטריצה המתקבלת מ-\(A\) ע"י החלפת העמודה ה-\(i\) ב-\(b\) (לכל \(n\geq i\in\MKnatural\)).. כעת נשים לב לכך שכל הרכיבים ב-\(A\) וב-\(A^{\left(i\right)}\) הם מספרים שלמים, ולכן מהנוסחה המפורשת של הדטרמיננטה נובע שגם \(\det A\) ו-\(\det A^{\left(i\right)}\) הם מספרים שלמים; מכאן שלכל \(n\geq i\in\MKnatural\) מתקיים:\[
\det A^{\left(i\right)}\equiv\left(\det A\right)\cdot x_{i}\mod N
\]בהערה על משפט 1.6 ראינו שאם \(\det A\) אינו זר ל-\(N\) וגם יש פתרונות מודולו \(N\), אז יש יותר מפתרון אחד (כי \(\gcd\left(\det A,N\right)>1\)); א"כ הוכחנו שאם קיים פתרון יחיד אז \(\overline{\det A}\in\left(\MKinteger/N\MKinteger\right)^{*}\). בנוסף, ניתן לראות כבר כעת שאם \(\overline{\det A}\in\left(\MKinteger/N\MKinteger\right)^{*}\) וגם יש פתרון מודולו \(N\) אז הפתרון יחיד, א"כ נשאר לנו להוכיח שאם \(\overline{\det A}\in\left(\MKinteger/N\MKinteger\right)^{*}\) אז קיים פתרון. נניח ש-\(\overline{\det A}\in\left(\MKinteger/N\MKinteger\right)^{*}\), בפרט \(\det A\neq0\) ולכן מכלל קרמר נובע שלכל \(n\geq i\in\MKnatural\) מתקיים (מעל \(\MKrational\)):\[
\frac{1}{\det A}\cdot\sum_{k=1}^{n}\left[A\right]_{ik}\cdot\det A^{\left(k\right)}=b_{k}
\]כלומר:\[
\sum_{k=1}^{n}\left[A\right]_{ik}\cdot\det A^{\left(k\right)}=\left(\det A\right)\cdot b_{k}
\]וזהו כבר שוויון ב-\(\MKinteger\) ולכן נקבל:\[
A\cdot\begin{bmatrix}\det A^{\left(1\right)}\\
\det A^{\left(2\right)}\\
\vdots\\
\det A^{\left(n\right)}
\end{bmatrix}\equiv\left(\det A\right)\cdot b\mod N
\]מההנחה ש-\(\overline{\det A}\in\left(\MKinteger/N\MKinteger\right)^{*}\) נובע שיש ל-\(\det A\) הופכי מודולו \(N\) ועבורו מתקיים:\[
A\cdot\begin{bmatrix}\left(\det A\right)^{-1}\cdot\det A^{\left(1\right)}\\
\left(\det A\right)^{-1}\cdot\det A^{\left(2\right)}\\
\vdots\\
\left(\det A\right)^{-1}\cdot\det A^{\left(n\right)}
\end{bmatrix}\equiv b\mod N
\]
משפט 1.38. יהיו \(a,b,c\in\MKinteger\), לקונגרואנציה \(ax^{2}+bx+c\equiv0\mod N\) יש פתרון אם"ם \(2a\in\left(\MKinteger/N\MKinteger\right)^{*}\) ו-\(b^{2}-4ac\) הוא שארית ריבועית מודולו \(N\) ובמקרה כזה כל \(d\in\MKinteger\) כך ש-\(d^{2}\equiv b^{2}-4ac\mod N\) נותן פתרון שהוא:\[
x\equiv\left(-b+d\right)\cdot\left(2a\right)^{-1}\mod N
\]
משפט 1.39. הלמה של הנזל21ערך בוויקיפדיה: קורט הנזל. יהי \(f\in\MKinteger\left[x\right]\) פולינום ויהיו \(p,e\in\MKnatural\) כך ש-\(p\) ראשוני, אם קיים \(a\in\MKinteger\) כך ש-\(f\left(a\right)\equiv0\mod p^{e}\) ו-\(f'\left(a\right)\not\equiv0\mod p\)22פולינום הנגזרת של פולינום בעל מקדמים שלמים שייך גם הוא לחוג הפולינומים מעל השלמים. אז קיים \(b\in\MKinteger\) כך ש-\(b\equiv a\mod p^{e}\) וגם \(f\left(b\right)\equiv0\mod p^{e+1}\)23נשים לב לכך שמכיוון ש-\(a\equiv b\mod p\) נקבל גם \(f'\left(b\right)\equiv f'\left(a\right)\not\equiv0\mod p\) ולכן ניתן להמשיך ו"להעלות" פתרונות עד לחזקה הרצויה.; בנוסף, אותו \(b\) הוא יחיד מודולו \(p^{e+1}\), כלומר לכל \(c\in\MKinteger\) המקיים \(c\equiv a\mod p^{e}\) וגם \(f\left(c\right)\equiv0\mod p^{e+1}\) מתקיים \(c\equiv b\mod p^{e+1}\). הפתרון שמביאה הוכחת המשפט הוא (לכל \(t\in\MKinteger\) המקיים את השקילות שלהלן):\[
b=a+t\cdot p^{e},\ t\equiv-f'\left(a\right)^{-1}\cdot\frac{f\left(a\right)}{p^{e}}\mod p
\]ומכאן הדרישה שיתקיים \(f'\left(a\right)\not\equiv0\mod p\).
הוכחה. נסמן \(n:=\deg f\), ראינו באינפי'1בפרק על פולינומי טיילור שלכל \(a\in\MKreal\) מתקיים24פולינום טיילור של פולינום, מסדר שווה לדרגת הפולינום, שווה לו עצמו בכל נקודה.:\[
P_{n,f,a}\left(x\right)=f\left(x\right)
\]בפרט הדבר נכון עבור \(a\in\MKinteger\) המקיים \(f\left(a\right)\equiv0\mod p^{e}\), נניח שאכן יש ל-\(f\) שורש מודולו \(p^{e}\) ויהי \(a\in\MKinteger\) שורש כזה. כעת נשים לבל לכך שלכל \(t\in\MKinteger\) מתקיים:\[
f\left(a+t\cdot p^{e}\right)=P_{n,f,a}\left(a+t\cdot p^{e}\right)=\sum_{k=0}^{n}\frac{f^{\left(k\right)}\left(a\right)}{k!}\cdot\left(a+t\cdot p^{e}-a\right)^{k}=\sum_{k=0}^{n}\frac{f^{\left(k\right)}\left(a\right)}{k!}\cdot\left(t\cdot p^{e}\right)^{k}
\]אך לכל \(2\leq k\in\MKnatural\) מתקיים \(\left(t\cdot p^{e}\right)^{k}\equiv t^{k}\cdot p^{e\cdot k}\equiv0\mod p^{e+1}\) ומכאן נובע כי לכל \(t\in\MKinteger\) מתקיים:\[
f\left(a+t\cdot p^{e}\right)=\sum_{k=0}^{n}\frac{f^{\left(k\right)}}{k!}\cdot\left(t\cdot p^{e}\right)^{k}\equiv f\left(a\right)+f'\left(a\right)\cdot t\cdot p^{e}\mod p^{e+1}
\]מהגדרה \(f\left(a\right)\equiv0\mod p^{e}\), א"כ קיים \(k\in\MKinteger\) כך ש-\(f\left(a\right)=k\cdot p^{e}\), יהי \(k\) כנ"ל (\(k:=\frac{f\left(a\right)}{p^{e}}\)) ומכאן שמתקיים:\[
f\left(a+t\cdot p^{e}\right)\equiv p^{e}\cdot\left(k+f'\left(a\right)\cdot t\right)\mod p^{e+1}
\]כעת, אם \(f'\left(a\right)\not\equiv0\mod p\) אז יש ל-\(f'\left(a\right)\) הופכי מודולו \(p\) ואותו הופכי מקיים:\[\begin{align*}
f\left(a+t\cdot p^{e}\right)\equiv0\mod p^{e+1} & \Longleftrightarrow k+f'\left(a\right)\cdot t\equiv0\mod p\\
& \Longleftrightarrow t\equiv-f'\left(a\right)^{-1}\cdot k\equiv-f'\left(a\right)^{-1}\cdot\frac{f\left(a\right)}{p^{e}}\mod p
\end{align*}\]אנחנו יודעים שלכל שורש \(b\in\MKinteger\) של \(f\) מודולו \(p^{e+1}\) קיים \(t\in\MKinteger\) כך ש-\(b\equiv a+t\cdot p^{e}\mod p^{e+1}\) ולכן השורה הקודמת מראה הן את הקיום של \(t\) כזה והן את יחידותו מודולו \(p\), יחידות זו נותנת גם את היחידות של מודולו \(p^{e+1}\) מפני שלכל \(t_{1},t_{2}\in\MKinteger\) כך ש-\(t_{1}\equiv t_{2}\mod p\) (כלומר \(p\mid t_{1}-t_{2}\)) מתקיים גם \(t_{1}\cdot p^{e}\equiv t_{2}\cdot p^{e}\) (כלומר \(p^{e+1}\mid\left(t_{1}-t_{2}\right)\cdot p^{e}\)).
2 פונקציות אריתמטיות
2.1 הגדרות
הגדרה 2.1. נסמן \(\MKclf:=\left\{ f:\MKnatural\rightarrow A\mid A\subseteq\MKcomplex\right\} \) (כלומר קבוצת הסדרות ב-\(\MKcomplex\)25ניתן היה להחליף את \(\MKcomplex\) בכל שדה או בכל קבוצה שמוגדרות עליה פעולות חיבור וכפל.) ונקרא ל-\(\MKclf\)קבוצת הפונקציות האריתמטיות.
\(\clubsuit\)
נתעניין בפונקציות \(f\in\MKclf\) המקיימות ש-\(f\left(n\right)\) תלוי בתכונות אריתמטיות של \(n\) (זו כמובן הסיבה לשם של \(\MKclf\)), קצת קשה להגדיר זאת...
\(\clubsuit\)
זה שונה מאד מהמובן הרגיל של כפליות.
\(\clubsuit\)
למרות שממבט ראשון הגדרת הקונבולוציה אינה סימטרית למעשה היא דווקא כן כזו מפני שאם נסמן \(D:=\left\{ \left(a,b\right)\in\MKinteger^{2}\mid a\cdot b=n\right\} \) נקבל:\[
\left(f*g\right)\left(n\right)=\sum_{\left(a,b\right)\in D}f\left(a\right)\cdot g\left(b\right)
\]
\(\clubsuit\)
כן, זה נראה קצת מגוחך ואולי זה באמת כך, כמובן שעבור \(k=0\) נקבל \(I_{0}\equiv1\).
\(\clubsuit\)
מהגדרה \(\sigma_{0}\left(n\right)\) הוא מספר המחלקים הטבעיים של \(n\).
\(\clubsuit\)
מספר משוכלל הוא כזה המקיים \(n=\sigma_{1}\left(n\right)\).
\(\clubsuit\)
כלומר אם \(n\) חופשי מריבועים אז \(\mu\left(n\right)\) הוא \(-1\) אם מספר הראשוניים המחלקים את \(n\) אי-זוגי ו-\(1\) אם הוא זוגי (בפרט \(\mu\left(1\right)=1\)).
הגדרה 2.2. נאמר על פונקציה אריתמטית \(f\) שהיא כפלית אם לכל \(n,m\in\MKnatural\) הזרים זה לזה מתקיים \(f\left(n\cdot m\right)=f\left(n\right)\cdot f\left(m\right)\), נסמן את קבוצת הפונקציות הכפליות ב-\(\MKclm\).
הגדרה 2.3. תהיינה \(f,g\in\MKclf\), נגדיר את הקונבולוציה\(f*g:\MKnatural\rightarrow\MKcomplex\) (נקראת גם קונבולוציית דיריכלה) ע"י (לכל \(n\in\MKnatural\)):\[
\left(f*g\right)\left(n\right):=\sum_{0<d\mid n}f\left(d\right)\cdot g\left(\frac{n}{d}\right)
\]
דוגמה 2.5. לכל \(k\in\MKnatural_{0}\) נגדיר את הפונקציה \(I_{k}:\MKnatural\rightarrow\MKnatural_{0}\) ע"י (לכל \(n\in\MKnatural\)):\[
I_{k}\left(n\right):=n^{k}
\]
דוגמה 2.6. לכל \(k\in\MKnatural_{0}\) נגדיר את \(\sigma_{k}:\MKnatural\rightarrow\MKnatural_{0}\) ע"י (לכל \(n\in\MKnatural\)):\[
\sigma_{k}\left(n\right):=\sum_{0<d\mid n}d^{k}
\]
דוגמה 2.8. תהא \(\mu:\MKnatural\rightarrow\left\{ -1,0,1\right\} \)פונקציית מביוס26ערך בוויקיפדיה: אוגוסט פרדיננד מביוס. המוגדרת ע"י (לכל \(n\in\MKnatural\)):
אם \(n\) אינו חופשי מריבועים אז \(\mu\left(n\right):=0\)
אם \(n\) חופשי מריבועים אז \(\mu\left(n\right):=\left(-1\right)^{k}\) כאשר \(k\) הוא מספר הראשוניים המחלקים את \(n\) (שמהגדרה שונים זה מזה)
דוגמה 2.9. תהא \(S:\MKnatural\rightarrow\MKnatural_{0}\) פונקציה המוגדרת ע"י \(S\left(n\right):=\left|\left\{ x^{2}\mid x\in\MKinteger/n\MKinteger\right\} \right|\), כלומר \(S\left(n\right)\) הוא מספר השאריות הריבועיות מודולו \(n\) (כולל \(0\)).
2.2 טענות
טענה 2.10. מתקיים \(\delta,I_{k},\sigma_{k}\phi,\mu,S\in\MKclm\) (לכל \(k\in\MKnatural_{0}\)), כלומר כל הפונקציות שראינו הן פונקציות כפליות.
\(\clubsuit\)
מכיוון שכבר ראינו ש-\(S\left(p\right)=\frac{p+1}{2}\) לכל \(2<p\in\MKnatural\) ראשוני (ו-\(S_{2}=2\)) נוכל לחשב את הערך של \(S\left(n\right)\) לכל \(n\) חופשי מריבועים.
משפט 2.11. לכל \(f,g,h\in\MKclf\) מתקיימים כל הפסוקים הבאים:
\(f*\left(g+h\right)=f*g+f*h\) - הקונבולוציה דיסטריבוטיבית ביחס לחיבור.
\(f*\delta=f\)
אם \(f\) ו-\(g\) כפליות אז גם \(f*g\) כפלית.
\(\mu*I_{0}=\delta\).
נוסחת ההיפוך של מביוס: אם \(\begin{alignedat}{1}g\left(n\right)=\sum_{0<d\mid n}f\left(d\right)\end{alignedat}
\) (לכל \(n\in\MKnatural\)) אז \(\begin{alignedat}{1}f\left(n\right)=\sum_{0<d\mid n}g\left(d\right)\cdot\mu\left(\frac{n}{d}\right)\end{alignedat}
\) (לכל \(n\in\MKnatural\)), ניתן לראות זאת גם כך: אם \(g=f*I_{0}\) אז \(f=g*\mu\).
טענה 2.12. מתקיים \(\phi*I_{0}=I_{1}\), כלומר לכל \(n\in\MKnatural\) מתקיים:\[
\sum_{0<d\mid n}\phi\left(d\right)=\sum_{0<d\mid n}\phi\left(d\right)\cdot I_{0}\left(\frac{n}{d}\right)=\left(\phi*I_{0}\right)\left(n\right)=I_{1}\left(n\right)=n
\]
הוכחה. נוכיח (באינדוקציה) שהטענה נכונה עבור חזקות של ראשוניים ומהכפליות של הקונבולוציה \(\phi*I_{0}\) ינבע שהטענה נכונה לכל מספר. יהי \(p\in\MKnatural\) ראשוני, מהגדרה מתקיים:\[
\sum_{0<d\mid p}\phi\left(d\right)=\phi\left(1\right)+\phi\left(p\right)=1+\left(p-1\right)=p
\]נניח באינדוקציה שהטענה נכונה עבור \(p^{e}\) ונוכיח עבור \(p^{e+1}\), המחלקים של \(p^{e+1}\) הם המחלקים של \(p^{e}\) יחד עם \(p^{e+1}\) עצמו.\[
\Rightarrow\sum_{0<d\mid p^{e+1}}\phi\left(d\right)=\phi\left(p^{e+1}\right)-\sum_{0<d\mid p^{e}}\phi\left(d\right)=\left(p^{e+1}-p^{e}\right)+p^{e}=p^{e+1}
\]\(\:\)
מסקנה 2.13. מתקיים \(\phi=I_{1}*\mu\), כלומר לכל \(n\in\MKnatural\) מתקיים:\[
\phi\left(n\right)=\sum_{0<d\mid n}I_{1}\left(d\right)\cdot\mu\left(\frac{n}{d}\right)=\sum_{0<d\mid n}d\cdot\mu\left(\frac{n}{d}\right)
\]
טענה 2.14. שקילויות נוספות, מתקיים:
\(\sigma_{0}=I_{0}*I_{0}\)
\(\sigma_{1}=I_{1}*I_{0}\)
מסקנה 2.15. מתקיים \(\sigma_{1}=\phi*\sigma_{0}\)27שימו לב לדמיון בין \(\phi*I_{0}=I_{1}\) ל-\(\phi*\sigma_{0}=\sigma_{1}\)..
הגדרה 3.1. לכל \(\overline{a}\in\left(\MKinteger/N\MKinteger\right)^{*}\) נסמן \(e_{N}\left(a\right):=\min\left\{ k\in\MKnatural\mid a^{k}\equiv1\mod N\right\} \) ונקרא ל-\(e_{N}\left(a\right)\)המעריך של \(a\) מודולו \(N\) (יש הקוראים לו גם האקספוננט או הסדר של \(a\) מודולו \(N\)).
טענה. לכל \(\overline{a}\in\left(\MKinteger/N\MKinteger\right)^{*}\) מתקיים \(e_{N}\left(a\right)\mid\phi\left(N\right)\).
הגדרה 3.2. יהי \(\overline{a}\in\left(\MKinteger/N\MKinteger\right)^{*}\), נאמר ש-\(a\) הוא שורש פרימיטיבי של \(N\) אם \(e_{N}\left(a\right)=\phi\left(N\right)\).
3.2 טענות
יהי \(1<N\in\MKnatural\).
טענה 3.3. לכל \(\overline{a}\in\left(\MKinteger/N\MKinteger\right)^{*}\) מתקיים \(e_{N}\left(a\right)\mid\phi\left(N\right)\).
טענה 3.4. לכל \(a\in\MKinteger\) זר ל-\(N\) ולכל \(i,j\in\MKnatural\)28למעשה ניתן היה לכתוב "לכל \(i,j\in\MKinteger\)" וכן במסקנות מהמשפט הקטן של פרמה וממשפט אוילר אבל לא התעסקנו בחזקות שאינן טבעיות בקורס., מתקיים \(a^{i}\equiv a^{j}\mod N\) אם"ם \(i\equiv j\mod e_{N}\left(a\right)\).
\(\clubsuit\)
הטענה מראה לנו שמההגדרה נובע שכדי לחשב חזקות בחשבון מודולו \(N\) ניתן לבצע חשבון מודולו \(e_{N}\left(a\right)\) על המעריך וזאת בתנאי שהבסיס זר ל-\(N\).
\(\clubsuit\)
בפרט לכל שורש פרימיטיבי \(a\in\MKinteger\) של \(N\) מתקיים (לכל \(i\in\MKnatural\)) \(a^{i}\equiv1\mod N\) אם"ם \(i\equiv0\mod{\phi}\left(N\right)\), כלומר אם"ם \(\phi\left(N\right)\mid i\).
\(\clubsuit\)
בפרט, לכל \(p\in\MKnatural\) ראשוני קיימים \(\phi\left(p-1\right)\) שורשים פרימיטיביים.
\(\clubsuit\)
השערת ארטין: בהינתן \(a\in\MKinteger\) שאינו ריבוע, האם קיימים אינסוף ראשוניים ש-\(a\) הוא שורש פרימיטיבי שלהם? ההשערה רוצה לומר שכן אך זו עדיין בעיה פתוחה במתמטיקה ולא קיים אפילו \(a\in\MKinteger\) אחד שאינו ריבוע שעבורו נפתרה הבעיה.
מסקנה 3.5. לכל שורש פרימיטיבי \(a\) של \(N\) מתקיים \(\left\{ a^{k}\mid k\in\MKnatural\right\} =\left(\MKinteger/N\MKinteger\right)^{*}\).
למה 3.6. יהי \(p\in\MKnatural\) ראשוני, ויהי \(p-1\geq d\in\MKnatural\) כך ש-\(d\mid p-1\), לפולינום \(x^{d}-1\) (מעל \(\MKinteger/p\MKinteger\)) יש \(d\) שורשים.
הוכחה. נסמן \(q:=\frac{p-1}{d}\) ונשים לב לכך שמתקיים:\[
x^{p-1}-1=\left(x^{d}\right)^{q}-1=\left(x^{d}-1\right)\cdot\sum_{k=0}^{q-1}\left(x^{d}\right)^{q-1-k}
\]כעת, מכיוון של-\(x^{p-1}-1\) יש \(p-1\) שורשים (המשפט הקטן של פרמה) נדע של-\(x^{d}-1\) יש \(d\) שורשים שהרי דרגת הפולינום הימני במכפלה היא \(\left(q-1\right)\cdot d=q\cdot d-d=p-1-d\) ולכן יש לו לכל היותר \(p-1-d\) שורשים.
למה 3.7. יהי \(n\in\MKnatural\), נסמן ב-\(D\) את קבוצת המחלקים הטבעיים של \(n\) ותהיינה \(f,g:D\rightarrow\MKcomplex\)29נשים לב ש-\(f\) ו-\(g\) אינן מוגדרות על כל הטבעיים ולכן א"א להשתמש בנוסחת ההיפוך של מביוס., אם לכל \(d\in D\) מתקיים \(\begin{alignedat}{1}\sum_{0<e\mid d}f\left(e\right)=\sum_{0<e\mid d}g\left(e\right)\end{alignedat}
\) אז \(f=g\).
הוכחה. נניח בשלילה שקיים \(d\in D\) כך ש-\(f\left(d\right)\neq g\left(d\right)\) ויהי \(d\) האיבר המינימלי המקיים זאת, א"כ לכל מחלק \(d>e\in\MKnatural\) של \(n\) מתקיים \(f\left(e\right)=g\left(e\right)\). נתון כי \(\begin{alignedat}{1}\sum_{0<e\mid d}f\left(d\right)=\sum_{0<e\mid d}g\left(d\right)\end{alignedat}
\) ומכאן שע"פ השורה הקודמת מתקיים \(f\left(d\right)=g\left(d\right)\) בסתירה להגדרת \(d\), א"כ הנחת השלילה אינה נכונה ולכל \(d\in D\) מתקיים \(f\left(d\right)=g\left(d\right)\).
משפט 3.8. יהי \(p\in\MKnatural\) ראשוני, לכל \(p>d\in\MKnatural\) המחלק את \(p-1\) מתקיים \(\phi\left(d\right)=\left|\left\{ \overline{a}\in\MKinteger/p\MKinteger\mid e_{p}\left(a\right)=d\right\} \right|\), כלומר לכל \(d\in\MKnatural\) כך ש-\(d\mid p-1\) קיימים \(\phi\left(d\right)\) איברים בשדה \(\MKfield_{p}\) שהמעריך שלהם הוא \(d\).
הוכחה. נסמן ב-\(D\) את קבוצת המחלקים הטבעיים של \(p-1\) ותהא \(\omega:D\rightarrow\MKnatural_{0}\) פונקציה המוגדרת ע"י (לכל \(d\in D\)):\[
\omega\left(d\right):=\left|\left\{ \overline{a}\in\MKinteger/p\MKinteger:e_{p}\left(a\right)=d\right\} \right|
\]ראינו בלמה 3.4 שלפולינום \(x^{d}-1\) יש בדיוק \(d\) שורשים לכל \(d\in D\), בנוסף אנחנו יודעים שלכל \(a\in\MKinteger\) כך ש-\(a^{d}-1\equiv0\mod p\) מתקיים \(e_{p}\left(a\right)\mid d\); מכאן שלכל \(d\in D\) מתקיים:\[
d=\sum_{0<e\mid d}\omega\left(e\right)
\]ולכן ע"פ למה 3.5 וטענה 2.3 מתקיים \(\phi\left(d\right)=\omega\left(d\right)=\left|\left\{ \overline{a}\in\MKinteger/p\MKinteger:e_{p}\left(a\right)=d\right\} \right|\) לכל \(d\in D\)30למעשה למה 3.5 אומרת ש-\(\phi\mid_{D}\) (הצמצום של \(\phi\) ל-\(D\)) שווה ל-\(\omega\)..
למה 3.9. יהיו \(2<p\in\MKnatural\) ראשוני ו-\(,t\in\MKnatural\) ויהיו \(a,b\in\MKinteger\) כך ש-\(a\) ו-\(b\) אינם מתחלקים ב-\(p\), אם \(a\not\equiv b\mod p^{t}\) אז \(a^{p}\not\equiv b^{p}\mod p^{t+1}\).
הוכחה. נניח ש-\(a\not\equiv b\mod p^{t}\) ונסמן \(s:=\max\left\{ i\in\MKnatural_{0}:p^{s}\mid a-b\right\} \), אם \(s=0\) אז \(a\not\equiv b\mod p\) ולכן מהמשפט הקטן של פרמה נובע שגם \(a^{p}\not\equiv b^{p}\mod p\) וממילא גם \(a^{p}\not\equiv b^{p}\mod p^{t+1}\). אחרת \(s\geq1\) וקיים \(k\in\MKinteger\) שאינו מתחלק ב-\(p\) כך ש-\(a=b+k\cdot p^{s}\), יהי \(k\) כנ"ל.\[\begin{align*}
\Rightarrow a^{p} & =\sum_{i=0}^{p}\begin{pmatrix}p\\
i
\end{pmatrix}\cdot b^{p-i}\cdot\left(k\cdot p^{s}\right)^{i}\\
& =b^{p}+p\cdot b^{p-1}\cdot k\cdot p^{s}+\begin{pmatrix}p\\
2
\end{pmatrix}\cdot b^{p-2}\cdot k^{2}\cdot p^{2s}+\sum_{i=2}^{p}\begin{pmatrix}p\\
i
\end{pmatrix}\cdot b^{p-i}\cdot k^{i}\cdot p^{s\cdot i}\\
& \equiv b^{p}+p\cdot b^{p-1}\cdot k\cdot p^{s}+\begin{pmatrix}p\\
2
\end{pmatrix}\cdot b^{p-2}\cdot k^{2}\cdot p^{2s}\mod p^{s+2}
\end{align*}\]נשים לב לכך שמתקיים \(p\mid\frac{p\cdot\left(p-1\right)}{2}=\begin{pmatrix}p\\
2
\end{pmatrix}\)31נזכור ש-\(p>2\). ומכאן שגם \(p^{s+2}\mid\begin{pmatrix}p\\
2
\end{pmatrix}\cdot b^{p-2}\cdot k^{2}\cdot p^{2s}\).\[
\Rightarrow a^{p}\equiv b^{p}+p\cdot b^{p-1}\cdot k\cdot p^{s}\mod p^{s+2}
\]נזכור ש-\(p\) אינו מחלק את \(b\) ואת \(k\) ומכאן ש-\(p\cdot b^{p-1}\cdot k\cdot p^{s}\not\equiv0\mod p^{s+2}\) וממילא \(a^{p}\not\equiv b^{p}\mod p^{s+2}\). מהגדרה \(t\geq s+1\) ולכן \(t+1\geq s+2\) ומכאן ש-\(a^{p}\not\equiv b^{p}\mod p^{t+1}\).
טענה 3.10. יהיו \(2<p\in\MKnatural\) ראשוני ו-\(a\in\MKinteger\) שורש פרימיטיבי של \(p\), אם \(a^{p-1}\not\equiv1\mod p^{2}\) אז \(a\) הוא שורש פרימיטיבי של \(p^{e}\) לכל \(e\in\MKnatural\), ואם \(a^{p-1}\equiv1\mod p^{2}\) אז \(a+p\) הוא שורש פרימיטיבי של \(p^{e}\) לכל \(e\in\MKnatural\).
הוכחה. נסמן \(x:=e_{p^{2}}\left(a\right)\), א"כ \(a^{x}\equiv1\mod p^{2}\) וממילא גם \(a^{x}\equiv1\mod p\) ולכן מהיות \(a\) שורש פרימיטיבי של \(p\) נובע ש-\(p-1\mid x\) (טענה 3.2), מצד שני מטענה 3.1 נדע שמתקיים \(x\mid\phi\left(p^{e}\right)=p^{e-1}\cdot\left(p-1\right)\) ולכן:
אם \(a^{p-1}\not\equiv1\mod p^{2}\) אז \(x\neq p-1\) ולכן (בגלל ש-\(e\mid p\cdot\left(p-1\right)\) וגם \(p-1\mid e\)32הנימוק הזה הוא שאינו עובד במקרה שבו \(p=2\): זה \(e\mid2\) וגם \(1\mid e\) לא אומר ש-\(e=2\), ייתכן ש-\(e=1\).) מתקיים בהכרח \(e=p\cdot\left(p-1\right)=\phi\left(p^{2}\right)\), כלומר \(a\) הוא שורש פרימיטיבי של \(p^{2}\).
אם \(a^{p-1}\equiv1\mod p^{2}\) אז מכיוון שמתקיים:\[\begin{align*}
\left(a+p\right)^{p-1} & =\sum_{i=0}^{p-1}\begin{pmatrix}p-1\\
i
\end{pmatrix}\cdot a^{p-1-i}\cdot p^{i}=a^{p-1}+\left(p-1\right)\cdot a^{p-2}\cdot p+\sum_{i=2}^{p-1}\begin{pmatrix}p-1\\
i
\end{pmatrix}\cdot a^{p-1-i}\cdot p^{i}\\
& \equiv a^{p-1}+\left(p-1\right)\cdot a^{p-2}\cdot p\equiv a^{p-1}-a^{p-2}\cdot p\not\equiv1\mod p^{2}
\end{align*}\]ובנוסף \(e_{p}\left(a+p\right)=e_{p}\left(a\right)=p-1\) נדע ש-\(p-1\mid e_{p^{2}}\left(a+p\right)\) ולכן מאותן סיבות שבסעיף הקודם מתקיים בהכרח \(e_{p^{2}}\left(a+p\right)=p\cdot\left(p-1\right)\) ו-\(a+p\) הוא שורש פרימיטיבי של \(p^{2}\).
הוכחה. כעת נוכיח באינדוקציה שכל שורש פרימיטיבי מודולו \(p^{2}\) הוא גם שורש פרימיטיבי של \(p^{e}\) לכל \(2<e\in\MKnatural\). יהי \(2\leq e\in\MKnatural\), יהי \(b\in\MKinteger\) שורש פרימיטיבי של \(p^{e}\), א"כ מתקיים \(b^{p^{e-2}\cdot\left(p-1\right)}\not\equiv1\mod p^{e}\), ולכן ע"פ למה 3.7 מתקיים \(b^{p^{e-1}\cdot\left(p-1\right)}\not\equiv1\mod p^{e+1}\). מצד שני מטענה 3.2 נובע שמתקיים \(p-1\mid e_{p^{e+1}}\left(b\right)\) ומטענה 3.1 מתקיים \(e_{p^{e+1}}\left(b\right)\mid\phi\left(p^{e+1}\right)=p^{e}\cdot\left(p-1\right)\) ועל כן בהכרח:\[
e_{p^{e+1}}\left(b\right)=p^{e}\cdot\left(p-1\right)
\]כלומר \(b\) הוא שורש פרימיטיבי מודולו \(p^{e+1}\).
טענה 3.11. יהיו \(2<p\in\MKnatural\) ראשוני, \(k\in\MKnatural\) ו-\(a\in\MKinteger\) שורש פרימיטיבי של \(p^{k}\)33מהטענה הקודמת נובע שאכן קיים \(a\) כזה., המספר האי-זוגי מבין \(a\) ו-\(a+p^{k}\)34בהכרח אחד מהם זוגי והאחר אי-זוגי ושניהם שורשים פרימיטיביים של \(p^{k}\) שהרי הם שקולים מודולו \(p^{k}\). הוא שורש פרימיטיבי של \(2p^{k}\).
הוכחה. ראשית נבחין שהדרישה לאי-זוגיות נובעת מהצורך הבסיסי שהשורש יהיה זר ל-\(2p^{k}\) ובפרט זר ל-\(2\), נסמן את האי-זוגי מבין \(a\) ו-\(a+p^{k}\) ב-\(b\). מטענה 3.2 נובע שמתקיים:\[
e_{p^{k}}\left(b\right)\mid e_{2p^{k}}\left(b\right),\ e_{2p^{k}}\left(b\right)\mid\phi\left(2p^{k}\right)
\]אבל לכל \(m\in\MKodd\) מתקיים \(\phi\left(2m\right)=\phi\left(m\right)\) ובפרט \(\phi\left(2p^{k}\right)=\phi\left(p^{k}\right)\). כעת נזכור ש-\(b\) הוא שורש פרימיטיבי מודולו \(p^{k}\) ועל כן \(e_{p^{k}}\left(b\right)=\phi\left(p^{k}\right)=\phi\left(2p^{k}\right)\) ומכאן שמתקיים:\[
\phi\left(2p^{k}\right)\mid e_{2p^{k}}\left(b\right)
\]ולכן בהכרח:\[
e_{2p^{k}}\left(b\right)=\phi\left(2p^{k}\right)
\]כלומר \(b\) הוא שורש פרימיטיבי מודולו \(2p^{k}\).
טענה 3.12. אם \(N\) מתחלק בשני ראשוניים אי-זוגיים שונים אז אין ל-\(N\) שורש פרימיטיבי.
הוכחה. נניח ש-\(N\) מתחלק בשני ראשוניים אי-זוגיים שונים ויהיו \(n,m\in\MKnatural\) זרים זה לזה כך ש-\(n\cdot m=N\) ולשניהם יש מחלק ראשוני אי-זוגי. נסמן \(l:=\MKlcm\left(\phi\left(n\right),\phi\left(m\right)\right)\), מהגדרה מתקיים \(\phi\left(n\right)\mid l\) וגם \(\phi\left(m\right)\mid l\) ולכן ממשפט אוילר נובע שלכל \(\overline{a}\in\left(\MKinteger/N\MKinteger\right)^{*}\) מתקיים:\[\begin{align*}
a^{l} & \equiv1\mod n\\
a^{l} & \equiv1\mod m
\end{align*}\]ומכאן שע"פ משפט השאריות הסיני מתקיים גם \(a^{l}\equiv1\mod N\)35קיימת רק שארית אחת מודולו \(N\) ששקולה ל-\(1\) בשני המודולוסים הזרים \(n\) ו-\(m\) והיא \(1\) מודולו \(N\).. כעת נשים לב לכך ש-\(\phi\left(n\right),\phi\left(m\right)\in\MKeven\) ולכן בהכרח \(l<\phi\left(n\right)\cdot\phi\left(m\right)=\phi\left(N\right)\) ומכאן שלכל \(\overline{a}\in\left(\MKinteger/N\MKinteger\right)^{*}\) מתקיים \(e_{N}\left(a\right)\leq l<\phi\left(N\right)\) ואין ל-\(N\) שורש פרימיטיבי.
טענה 3.13. אם \(N\) מתחלק ב-\(4\) ובראשוני אי-זוגי אז אין ל-\(N\) שורשים פרימיטיביים.
הוכחה. נניח ש-\(N\) מתחלק ב-\(4\) ובראשוני אי-זוגי ויהיו \(k,m\in\MKnatural\) כך ש-\(2^{k}\cdot m=N\) ו-\(m\in\MKodd\), מהנתון נובע ש-\(2\leq k\), \(3\leq m\) ו-\(\gcd\left(2^{k},m\right)=1\). נסמן \(l:=\MKlcm\left(\phi\left(2^{k}\right),\phi\left(m\right)\right)\), מהגדרה מתקיים \(\phi\left(2^{k}\right)\mid l\) וגם \(\phi\left(m\right)\mid l\) ולכן ממשפט אוילר נובע שלכל \(\overline{a}\in\left(\MKinteger/N\MKinteger\right)^{*}\) מתקיים:\[\begin{align*}
a^{l} & \equiv1\mod 2^{k}\\
a^{l} & \equiv1\mod m
\end{align*}\]ומכאן שע"פ משפט השאריות הסיני מתקיים גם \(a^{l}\equiv1\mod N\). כעת נשים לב לכך ש-\(\phi\left(2^{k}\right),\phi\left(m\right)\in\MKeven\) ולכן בהכרח \(l<\phi\left(2^{k}\right)\cdot\phi\left(m\right)=\phi\left(N\right)\) ומכאן שלכל \(\overline{a}\in\left(\MKinteger/N\MKinteger\right)^{*}\) מתקיים \(e_{N}\left(a\right)\leq l<\phi\left(N\right)\) ואין ל-\(N\) שורש פרימיטיבי.
טענה 3.14. אם קיים \(2<k\in\MKnatural\) כך ש-\(N=2^{k}\) אז אין ל-\(N\) שורש פרימיטיבי.
הוכחה. נניח שקיים \(k\) כנ"ל ונוכיח את הטענה באינדוקציה על \(k\). עבור \(k=3\) מתקיים \(2^{k}=8\) ול-\(8\) אכן אין שורשים פרימיטיביים:\[\begin{align*}
1^{1} & \equiv1\mod 8 & 5^{2} & \equiv1\mod 8\\
3^{2} & \equiv1\mod 8 & 7^{2} & \equiv1\mod 8
\end{align*}\]כעת נניח באינדוקציה שהטענה נכונה עבור \(3\leq k\in\MKnatural\) כלשהו ונוכיח עבור \(k+1\). נסמן \(n:=2^{k}\), ויהי \(a\in\MKinteger\) זר ל-\(2^{k+1}\) (כלומר \(a\in\MKodd\)). מטענה 3.1 נקבל ש-\(e_{n}\left(a\right)\mid\phi\left(n\right)=2^{k-1}\) ומהנחת האינדוקציה נובע ש-\(e_{n}\left(a\right)<\phi\left(n\right)=2^{k-1}\) וממילא מתקיים:\[
a^{\left(2^{k-2}\right)}\equiv1\mod 2^{k}
\]א"כ יהי \(q\in\MKinteger\) כך ש-\(a^{\left(2^{k-2}\right)}=1+2^{k}\cdot q\).\[
\Rightarrow a^{\left(2^{k-1}\right)}=\left(1+2^{k}\cdot q\right)^{2}=1+2\cdot2^{k}\cdot q+2^{2k}\cdot q^{2}\equiv1\mod 2^{k+1}
\]אבל \(2^{k-1}<2^{k}=\phi\left(2^{k+1}\right)\) ומכאן ש-\(a\) אינו שורש פרימיטיבי מודולו \(2^{k+1}\).
מסקנה 3.15. יש ל-\(N\) שורש פרימיטיבי אם"ם קיים \(2<p\in\MKnatural\) ראשוני כך ש-\(N\in\left\{ 2,4\right\} \cup\left\{ p^{k}\mid k\in\MKnatural\right\} \cup\left\{ 2p^{k}\mid k\in\MKnatural\right\} \), כלומר אם"ם \(N\) הוא \(2\), \(4\), חזקה של ראשוני אי-זוגי או \(2\) כפול חזקה של ראשוני אי-זוגי.
4 שאריות ריבועיות וחוק ההדדיות הריבועית
4.1 הגדרות
הגדרה 4.1. נאמר ש-\(a\in\MKinteger\) (או \(\overline{a}\in\MKinteger/N\MKinteger\)) הוא שארית ריבועית מודולו \(N\) אם קיים \(b\in\MKinteger\) כך ש-\(b^{2}\equiv a\mod N\).
הגדרה 4.2. סמל לז'נדר36ערך בוויקיפדיה:אדריאן-מארי לז'נדר. נסמן \(P:=\MKprime\setminus\left\{ 2\right\} \), הסמל של לז'נדר (נקרא גם סימן לז'נדר) הוא הפונקציה \(\left(\begin{array}{c}
\cdot\\
\hline \cdot
\end{array}\right):\MKinteger\times P\rightarrow\left\{ 1,-1,0\right\} \) המוגדרת ע"י (לכל \(a\in\MKinteger\) ו-\(2<p\in\MKprime\)):\[
\left(\begin{array}{c}
a\\
\hline p
\end{array}\right):=\begin{cases}
0 & a\equiv0\mod p\\
1 & a\not\equiv0\mod p,\ \exists x\in\MKinteger:x^{2}\equiv a\mod p\\
-1 & a\not\equiv0\mod p,\ \nexists x\in\MKinteger:x^{2}\equiv a\mod p
\end{cases}
\]או בעברית: סימן לז'נדר של \(a\) הוא \(0\) אם \(a\) הוא \(0\) מודולו \(p\), \(1\) אם הוא שארית ריבועית שונה מאפס מודולו \(p\) ו-\(-1\) אחרת.
טענה 4.3. לכל \(2<p\in\MKnatural\) ראשוני ולכל \(a,b\in\MKinteger\) מתקיים:\[
\left(\begin{array}{c}
a\\
\hline p
\end{array}\right)=\left(\begin{array}{c}
b\\
\hline p
\end{array}\right)\Longleftrightarrow a\equiv b\mod p
\]
הגדרה 4.4. שארית מינימלית יהיו \(2<p\in\MKnatural\) ראשוני ו-\(a\in\MKinteger\), ישנן שתי הגדרות לשארית מינימלית שמאחוריהן עומד אותו רעיון:
השארית המינימלית של \(a\) מודולו \(p\) היא האיבר היחיד בקטע \(\left(-\frac{p-1}{2},\frac{p-1}{2}\right)\) השקול ל-\(a\) מודולו \(p\).
השארית המינימלית של \(a\) מודולו \(p\) היא האיבר היחיד בקטע \(\left[0,p\right)\) השקול ל-\(a\) מודולו \(p\).
נסמן את השארית המינימלית של \(a\) מודולו ע"י \(\left\{ a\right\} _{p}\).
4.2 טענות
טענה 4.5. יהי \(2<p\in\MKnatural\) מספר ראשוני, מתקיים:\[
\left|\left\{ x^{2}:0\neq x\in\MKfield_{p}\right\} \right|=\frac{p-1}{2}
\]כלומר מספר השאריות הריבועיות השונות מ-\(0\) בשדה \(\MKinteger/p\MKinteger\) (או מספר השאריות הריבועיות השונות מאפס מודולו \(p\)) הוא \(\frac{p-1}{2}\).
\(\clubsuit\)
הריבועים הם כל הריבועים של \(\frac{p-1}{2}\) האיברים ה"ראשונים" בשדה מפני שהשאר הם הנגדיים שלהם.
\(\clubsuit\)
כרגיל מהכפליות נובע שמספיק לבדוק את הסמל על ראשוניים כדי להכיר אותו כראוי.
\(\clubsuit\)
בתרגילי החזרה למבחן הוכחנו שאם \(p\equiv3\mod 4\) אז \(\frac{p-1}{2}!\equiv\pm1\mod p\), הדרך לעשות זאת הייתה להראות שמתקיים \(\left(\frac{p-1}{2}!\right)^{2}\equiv1\mod p\).
\(\clubsuit\)
אם במקום להשתמש בעובדה ש-\(a\) אי-זוגי היינו מניחים ש-\(a=2\) אז היינו מקבלים שמתקיים:\[
\frac{p^{2}-1}{8}=\left(a-1\right)\cdot\frac{p^{2}-1}{8}\equiv p\cdot\left(n+\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor \frac{ka}{p}\right\rfloor \right)\equiv n+\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor \frac{ka}{p}\right\rfloor \mod 2
\]והיות שלכל \(\frac{p-1}{2}\geq k\in\MKnatural\) מתקיים \(\left\lfloor \frac{2k}{p}\right\rfloor =0\) היה נובע מזה שמתקיים:\[
\frac{p^{2}-1}{8}\equiv n\mod 2
\]ומממילא \(\left(-1\right)^{\frac{p^{2}-1}{8}}=\left(-1\right)^{n}\) ולכן גם:\[
\left(\begin{array}{c}
2\\
\hline p
\end{array}\right)=\left(-1\right)^{\frac{p^{2}-1}{8}}
\]
\(\clubsuit\)
חוק ההדדיות הריבועית, הכפליות של סמל לז'נדר והעובדה שמהגדרה סמל לז'נדר עובד לפי המודולוס37כלומר אם מספר כלשהו הוא שארית ריבועית אז כל מספר אחר ששקול לו לפי המודולוס גם הוא שארית ריבועית באותו מודולוס. מאפשרים לנו לבדוק את מספר שלם כלשהו הוא שארית ריבועית במהירות רבה ע"י השלבים הבאים:
אם המספר שנמצא בחלק העליון של הסמל גדול מהתחתון אז כותבים אותו מודולו התחתון.
אם הוא אינו ראשוני אז מפרקים אותו לראשוניים וכותבים את סמל לז'נדר כמכפלה של כל אחת מהחזקות בנפרד.
מחזקות זוגיות ניתן להתעלם ולחזקות אי-זוגיות ניתן להתייחס כהעלקה בחזקת \(1\).
כעת כל המספרים בסמלים הם ראשוניים וניתן להשתמש במשפט ההדדיות הריבועית - אם אחד מהראשוניים שקול ל-\(1\) מודולו \(4\) ניתן "להפוך" את הסמל ללא שינוי נוסף, אחרת יש להוסיף סימן מינוס בחוץ.
חוזרים על ארבעת השלבים הקודמים עבור כל אחד מהסמלים במכפלה, המספרים הולכים וקטנים במהירות עד שניתן לבדוק ישירות את סמלי לז'נדר הנותרים באופן ישיר, בנוסף התהליך הזה ייעצר רק כאשר בחלק העליון של הסמל יופיע הראשוני \(2\)38סמל לז'נדר אינו מוגדר עבורו ולכן א"א "להפוך" את הסמל כשמגיעים אליו. ואז ניתן להשתמש במסקנה 4.7.
\(\clubsuit\)
כדי להוכיח את הטענה נמיר השאלה אם \(a\in\MKinteger\) הוא שארית ריבועית מודולו \(p^{k}\) כאשר \(p\) ראשוני בשאלה אם יש לפולינום \(x^{2}-a\) שורש מודולו \(p\) ואז נשתמש בלמה של הנזל39הנגזרת (\(2x\)) לעולם לא תתאפס מפני ש-\(2\) זר ל-\(p^{e}\) לכל \(e\in\MKnatural\) ואם \(s^{2}\equiv a\mod p^{e}\) עבור \(e\in\MKnatural\) כלשהו אז העובדה ש-\(a\) זר ל-\(p^{e}\) מחייבת שגם \(s\) זר ל-\(p^{e}\)..
\(\clubsuit\)
ממסקנה 1.15 נובע שאם מספר \(a\in\MKinteger\) הוא שארית ריבועית מודולו \(p\) ראשוני לכל ראשוני המופיע בפירוק של מספר \(1<N\in\MKnatural\) אז הוא גם שארית ריבועית מודולו \(N\).
\(\clubsuit\)
מה קורה כאשר מדובר במעריך גדול מ-\(2\)? בכיתה עסקנו רק במקרים שבהם המעריך הוא ראשוני (בטענה הבאה).
הוכחה. כל מה שצריך להוכיח הוא שלכל \(a,b\in\MKinteger\) מתקיים \(a^{2}\equiv b^{2}\mod p\Longleftrightarrow a\equiv\pm b\mod p\) וזה קורה מכיוון ש-\(a^{2}-b^{2}\equiv\left(a+b\right)\left(a-b\right)\mod p\) ו-\(\MKinteger/p\MKinteger\) הוא שדה.
טענה 4.6. יהיו \(2<p\in\MKnatural\) ראשוני \(g\in\MKinteger\) שורש פרימיטיבי של \(p\) ו-\(a\in\MKinteger\) כך ש-\(a\not\equiv0\mod p\), מהגדרה קיים \(n\in\MKnatural\) כך ש-\(g^{n}\equiv a\mod p\), יהי \(n\) כנ"ל; הפסוקים הבאים שקולים:
\(a\) הוא שארית ריבועית מודולו \(p\).
\(n\) זוגי40הזוגיות של \(n\) מוגדרת היטב מפני ש-\(p-1\) זוגי ולכן מהמשפט הקטן של פרמה לכל \(m\in\MKinteger\) כך ש-\(g^{m}\equiv a\mod p\)\(m\) זוגי..
\(2e_{p}\left(a\right)\mid p-1\) או אם תרצו \(e_{p}\left(a\right)\mid\frac{p-1}{2}\) או \(2\mid\frac{p-1}{e_{p}\left(a\right)}\), בקיצור \(\frac{p-1}{2e_{p}\left(a\right)}\in\MKinteger\).
הוכחה. נוכיח תחילה ששני הסעיפים הראשונים שקולים זה לזה:
\(\Leftarrow\) נניח ש-\(a\) הוא שארית ריבועית מודולו \(p\) ויהי \(s\in\MKinteger\) כך ש-\(s^{2}\equiv a\mod p\). יהי \(m\in\MKnatural\) כך ש-\(g^{m}\equiv s\mod p\), א"כ מתקיים \(g^{2m}\equiv s^{2}\equiv a\equiv g^{n}\mod p\) ולכן מהמשפט הקטן של פרמה נובע ש-\(2m\equiv n\mod p-1\) וממילא גם \(2m\equiv n\mod 2\) ו-\(n\in\MKeven\).
\(\Rightarrow\) נניח ש-\(n\) זוגי ונסמן \(s:=g^{\frac{n}{2}}\in\MKinteger\), מכאן שמתקיים \(s^{2}\equiv g^{n}\equiv a\mod p\) ו-\(a\) הוא שארית ריבועית מודולו \(p\).
הוכחה. כעת נעבור להוכחת השקילות בין שני הסעיפים האחרונים:
\(\Leftarrow\) נניח ש-\(n\) זוגי ויהי \(m\in\MKnatural\) כך ש-\(n=2m\),\[\begin{align*}
\Rightarrow a^{\frac{p-1}{2}} & \equiv\left(g^{n}\right)^{\frac{p-1}{2}}\equiv g^{n\cdot\frac{p-1}{2}}\equiv g^{2m\cdot\frac{p-1}{2}}\\
& \equiv g^{m\cdot\left(p-1\right)}\equiv\left(g^{p-1}\right)^{m}\equiv1^{m}\equiv1\mod p
\end{align*}\]ולכן מטענה 3.1 נובע ש-\(e_{p}\left(a\right)\mid\frac{p-1}{2}\).
\(\Rightarrow\) נניח ש-\(e_{p}\left(a\right)\mid\frac{p-1}{2}\) ויהי \(m\in\MKnatural\) כך ש-\(m\cdot e_{p}\left(a\right)=\frac{p-1}{2}\).\[
\Rightarrow g^{n\cdot\frac{p-1}{2}}\equiv\left(g^{n}\right)^{\frac{p-1}{2}}\equiv a^{\frac{p-1}{2}}\equiv a^{m\cdot e_{p}\left(a\right)}\equiv\left(a^{e_{p}\left(a\right)}\right)^{m}\equiv1^{m}\equiv1\mod p
\]מהיות \(g\) שורש פרימיטיבי ומטענה 3.2 נובע שמתקיים \(n\cdot\frac{p-1}{2}\equiv0\mod p-1\), כלומר \(p-1\mid n\cdot\frac{p-1}{2}\) ולכן \(n\) מוכרח להיות זוגי.
טענה 4.7. הסמל של לז'נדר הוא פונקציה כפלית, לכל \(2<p\in\MKnatural\) ראשוני ולכל \(a,b\in\MKinteger\) מתקיים:\[
\left(\begin{array}{c}
ab\\
\hline p
\end{array}\right)=\left(\begin{array}{c}
a\\
\hline p
\end{array}\right)\left(\begin{array}{c}
b\\
\hline p
\end{array}\right)
\]
הוכחה. יהי \(2<p\in\MKnatural\) ראשוני, יהיו \(a,b\in\MKinteger\). ונניח תחילה ש-\(a\) ו-\(b\) אינם מתחלקים ב-\(p\). יהי \(g\) שורש פרימיטיבי של \(p\) ויהיו \(n,m\in\MKnatural\) כך ש-\(g^{n}\equiv a\mod p\) ו-\(g^{m}\equiv b\mod p\).\[
\Rightarrow ab\equiv g^{n+m}\mod p
\]נשים לב ש-\(n+m\in\MKeven\) אם"ם \(n,m\in\MKeven\) או ש-\(n,m\in\MKodd\), מהטענה הקודמת (4.2) נובע ש-\(g^{n+m}\) הוא שארית ריבועית מודולו \(p\) אם"ם \(g^{n}\) ו-\(g^{m}\) הם שאריות ריבועיות או ששניהם אינם שאריות ריבועיות, כלומר \(ab\) הוא שארית ריבועית אם"ם \(a\) ו-\(b\) הם שאריות ריבועיות או ששניהם אינם שאריות ריבועיות.\[
\Rightarrow\left(\begin{array}{c}
ab\\
\hline p
\end{array}\right)=\left(\begin{array}{c}
a\\
\hline p
\end{array}\right)\left(\begin{array}{c}
b\\
\hline p
\end{array}\right)
\]אם \(a\) ו/או \(b\) מתחלקים ב-\(p\) אז גם \(ab\) מתחלק ב-\(p\) ולכן סמל לז'נדר שלו הוא \(0\) ומהגדרה גם אגף שמאל הוא \(0\).
משפט 4.8. מבחן אוילר לכל \(2<p\in\MKnatural\) ראשוני ולכל \(a\in\MKinteger\) מתקיים:\[
\left(\begin{array}{c}
a\\
\hline p
\end{array}\right)\equiv a^{\frac{p-1}{2}}\mod p
\]
הוכחה. יהיו \(2<p\in\MKnatural\) ראשוני ו-\(a\in\MKinteger\), אם \(a\equiv0\mod p\) אז הטענה טריוויאלית, א"כ נניח ש-\(a\not\equiv0\mod p\). יהי \(g\) שורש פרימיטיבי של \(p\) ויהי \(n\in\MKnatural\) כך ש-\(g^{n}\equiv a\mod p\); מטענה 4.2 נובע שאם \(a\) שארית ריבועית אז \(n\in\MKeven\) ולכן גם:\[
a^{\frac{p-1}{2}}\equiv\left(g^{n}\right)^{\frac{p-1}{2}}\equiv\left(g^{p-1}\right)^{\frac{n}{2}}\equiv1^{\frac{n}{2}}\equiv1\equiv\left(\begin{array}{c}
a\\
\hline p
\end{array}\right)\mod p
\]ואם \(a\) אינו שארית ריבועית אז \(n\in\MKodd\) ולכן גם41אנחנו יודעים ש-\(g^{\frac{p-1}{2}}\not\equiv1\mod p\) ושאם נעלה את \(g^{\frac{p-1}{2}}\) בריבוע נקבל את \(1\) מודולו \(p\), בשדה (ו-\(\MKinteger/p\MKinteger\) הוא שדה) יש רק שני שורשים ריבועיים של \(1\) והם \(\pm1\) ומכאן ש-\(g^{\frac{p-1}{2}}\equiv-1\mod p\).:\[
a^{\frac{p-1}{2}}\equiv\left(g^{n}\right)^{\frac{p-1}{2}}\equiv\left(g^{\frac{p-1}{2}}\right)^{n}\equiv\left(-1\right)^{n}\equiv-1\equiv\left(\begin{array}{c}
a\\
\hline p
\end{array}\right)\mod p
\]
מסקנה 4.9. לכל \(2<p\in\MKnatural\) ראשוני מתקיים:\[
\left(\begin{array}{c}
-1\\
\hline p
\end{array}\right)=\left(-1\right)^{\frac{p-1}{2}}
\]
משפט 4.10. הלמה של גאוס יהיו \(2<p\in\MKnatural\) ראשוני ו-\(a\in\MKinteger\) זר ל-\(p\) ונסמן ב-\(n\) את מספר השאריות המינימליות השליליות42נעבוד ע"פ ההגדרה הראשונה של שאריות מינימליות. בקבוצה \(\left\{ \left\{ i\cdot a\right\} _{p}\mid\frac{p-1}{2}\geq i\in\MKnatural\right\} \), מתקיים:\[
\left(\begin{array}{c}
a\\
\hline p
\end{array}\right)=\left(-1\right)^{n}
\]
הוכחה. נסמן \(S:=\left\{ \left\{ i\cdot a\right\} _{p}\mid\frac{p-1}{2}\geq i\in\MKnatural\right\} \), ותהיינה \(s_{1},s_{2},\ldots,s_{n}\in S\) כל השאריות השליליות ב-\(S\) ו-\(r_{1},r_{2},\ldots,r_{m}\in S\) יתר השאריות ב-\(S\). נשים לב לכך שלכל \(\frac{p-1}{2}\geq i,j\in\MKnatural\) כך ש-\(i\neq j\) מתקיים \(i\cdot a\not\equiv-j\cdot a\mod p\): משום שאחרת יתקיים גם \(a\cdot\left(i+j\right)\equiv0\mod p\) ומכיוון ש-\(a\) זר ל-\(p\) נדע ש-\(i+j\equiv0\mod p\) בסתירה לכך ש\(i\) ו-\(j\) הם טבעיים שונים הקטנים מ-\(\frac{p-1}{2}\) ולכן סכומם אינו עולה על \(p-1\); א"כ לכל \(n\geq i\in\MKnatural\) ולכל \(m\geq j\in\MKnatural\) מתקיים \(-s_{i}\not\equiv r_{j}\mod p\) ומכאן שע"פ עקרון שובך היונים מתקיים43מהגדרה לכל \(n\geq i\in\MKnatural\) מתקיים \(0<-s_{i}\leq\frac{p-1}{2}\), כמו כן \(r_{j}\not\equiv0\mod p\) לכל \(m\geq j\in\MKnatural\) מפני ש-\(a\) זר ל-\(p\).:\[
\left\{ i\in\MKnatural\mid i\leq\frac{p-1}{2}\right\} =\left\{ -s_{1},-s_{2},\ldots,-s_{n},r_{1},r_{2},\ldots,r_{m}\right\}
\]\[
\Rightarrow\frac{p-1}{2}!=\prod_{i=1}^{n}\left(-s_{i}\right)\cdot\prod_{j=1}^{m}r_{j}=\left(-1\right)^{n}\cdot\prod_{i=1}^{n}s_{i}\cdot\prod_{j=1}^{m}r_{j}
\]כעת נזכור שמהגדרה \(S=\left\{ s_{1},s_{2},\ldots,s_{n},r_{1},r_{2},\ldots,r_{m}\right\} \) ולכן:\[
\prod_{i=1}^{n}s_{i}\cdot\prod_{j=1}^{m}r_{j}\equiv\prod_{i=1}^{\frac{p-1}{2}}\left(i\cdot a\right)\equiv\frac{p-1}{2}!\cdot a^{\frac{p-1}{2}}\mod p
\]\[
\Rightarrow\frac{p-1}{2}!=\left(-1\right)^{n}\cdot\frac{p-1}{2}!\cdot a^{\frac{p-1}{2}}\mod p
\]העצרת המופיעה בשקילות היא מכפלה של מספרים זרים ל-\(p\) ולכן היא שווה למספר זר ל-\(p\) וניתן לחלק בה את שני האגפים.\[\begin{align*}
& \Rightarrow1\equiv\left(-1\right)^{n}\cdot a^{\frac{p-1}{2}}\mod p\\
& \Rightarrow\left(-1\right)^{n}\equiv a^{\frac{p-1}{2}}\mod p
\end{align*}\]וממבחן אוילר נקבל את המבוקש.
הוכחה. נשים לב לכך שלכל \(\frac{p-1}{4}\geq i\in\MKnatural\) מתקיים \(\left\{ 2i\right\} _{p}>0\) ולכל \(i\in\MKnatural\) כך ש-\(\frac{p-1}{4}<i\leq\frac{p-1}{2}\) מתקיים \(\left\{ 2i\right\} _{p}<0\), א"כ מספר השאריות המינימליות השליליות בקבוצה \(\left\{ \left\{ 2i\right\} _{p}\mid\frac{p-1}{2}\geq i\in\MKnatural\right\} \) הוא \(n:=\frac{p-1}{2}-\left\lfloor \frac{p-1}{4}\right\rfloor \) ומכאן שע"פ הלמה של גאוס מתקיים:\[
\left(\begin{array}{c}
2\\
\hline p
\end{array}\right)=\left(-1\right)^{n}
\]יהיו \(q\in\MKinteger\) ו-\(8>r\in\MKnatural_{0}\) כך ש-\(p=8q+r\)44מהגדרה \(q\in\MKnatural\) ו-\(r\in\MKodd\)., נבחין כי:\[\begin{align*}
\frac{p-1}{2} & =\begin{cases}
4q & r=1\\
4q+1 & r=3\\
4q+2 & r=5\\
4q+3 & r=7
\end{cases} & \left\lfloor \frac{p-1}{4}\right\rfloor & =\begin{cases}
2q & r=1\\
2q & r=3\\
2q+1 & r=5\\
2q+1 & r=7
\end{cases}
\end{align*}\]\[
\Rightarrow\frac{p-1}{2}-\left\lfloor \frac{p-1}{4}\right\rfloor =\begin{cases}
6q & r=1\\
6q+1 & r=3\\
6q+3 & r=5\\
6q+4 & r=7
\end{cases}
\]\[
\Rightarrow\left(\begin{array}{c}
2\\
\hline p
\end{array}\right)=\left(-1\right)^{n}=\begin{cases}
1 & p\equiv1\lor p\equiv7\mod 8\\
-1 & p\equiv3\lor p\equiv5\mod 8
\end{cases}
\]
למה 4.12. יהי \(a\in\MKinteger\) אי-זוגי זר לראשוני \(2<p\in\MKnatural\), נסמן:\[
t:=\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor \frac{ka}{p}\right\rfloor
\]מתקיים:\[
\left(\begin{array}{c}
a\\
\hline p
\end{array}\right)=\left(-1\right)^{t}
\]
הוכחה. נבחין כי \(\left\lfloor \frac{ka}{p}\right\rfloor \) היא המנה של חלוקת \(ka\) ב-\(p\) עם שארית, מכאן (נשתמש בסימוני הוכחת הלמה של גאוס) שמתקיים:\[\begin{align*}
\sum_{k=1}^{\frac{p-1}{2}}ka & =\sum_{k=1}^{\frac{p-1}{2}}p\cdot\left\lfloor \frac{ka}{p}\right\rfloor +\sum_{i=1}^{n}\left(p+s_{i}\right)+\sum_{j=1}^{m}r_{j}\\
& =np+\sum_{k=1}^{\frac{p-1}{2}}p\cdot\left\lfloor \frac{ka}{p}\right\rfloor +\sum_{i=1}^{n}s_{i}+\sum_{j=1}^{m}r_{j}\\
& =p\cdot\left(n+\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor \frac{ka}{p}\right\rfloor \right)+\sum_{i=1}^{n}s_{i}+\sum_{j=1}^{m}r_{j}
\end{align*}\]וגם:\[
\sum_{k=1}^{\frac{p-1}{2}}k=\sum_{i=1}^{n}\left(-s_{i}\right)+\sum_{j=1}^{m}r_{j}
\]\[
\Rightarrow\left(a-1\right)\cdot\sum_{k=1}^{\frac{p-1}{2}}k=\sum_{k=1}^{\frac{p-1}{2}}ka-\sum_{k=1}^{\frac{p-1}{2}}k=p\cdot\left(n+\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor \frac{ka}{p}\right\rfloor \right)+2\cdot\sum_{i=1}^{n}s_{i}
\]אבל:\[
\sum_{k=1}^{\frac{p-1}{2}}k=\frac{\left(p-1\right)\left(\frac{p-1}{2}+1\right)}{4}=\frac{\left(p-1\right)\cdot\frac{p+1}{2}}{4}=\frac{p^{2}-1}{8}
\]\[
\Rightarrow\left(a-1\right)\cdot\frac{p^{2}-1}{8}=p\cdot\left(n+\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor \frac{ka}{p}\right\rfloor \right)+2\cdot\sum_{i=1}^{n}s_{i}
\]ומכאן נובע כי (נזכור ש-\(p\) ו-\(a\) אי-זוגיים):\[
0\equiv\left(a-1\right)\cdot\frac{p^{2}-1}{8}\equiv p\cdot\left(n+\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor \frac{ka}{p}\right\rfloor \right)\equiv n+\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor \frac{ka}{p}\right\rfloor \mod 2
\]\[\begin{align*}
& \Rightarrow t=\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor \frac{ka}{p}\right\rfloor \equiv n\mod 2\\
& \Rightarrow\left(-1\right)^{t}\equiv\left(-1\right)^{n}\mod 2
\end{align*}\]ולכן ע"פ הלמה של גאוס מתקיים:\[
\left(-1\right)^{t}=\left(-1\right)^{n}=\left(\begin{array}{c}
a\\
\hline p
\end{array}\right)
\]
משפט 4.13. חוק ההדדיות הריבועית יהיו \(2<p,q\in\MKprime\) שונים זה מזה, מתקיים:\[
\left(\begin{array}{c}
q\\
\hline p
\end{array}\right)\cdot\left(\begin{array}{c}
p\\
\hline q
\end{array}\right)=\left(-1\right)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}
\]או בעברית פשוטה:
אם \(p\equiv1\mod 4\) ו/או \(q\equiv1\mod 4\) אז \(p\) הוא שארית ריבועית מודולו \(q\) אם"ם \(q\) הוא שארית ריבועית מודולו \(p\) (כלומר סימני לז'נדר שלהם זהים).
אם \(p\equiv q\equiv3\mod 4\) אז \(p\) הוא שארית ריבועית מודולו \(q\) אם"ם \(q\)אינו שארית ריבועית מודולו \(p\) (כלומר סימני לז'נדר שלהם מנוגדים).
הוכחה. נתבונן בשריג45דמיינו את הקבוצה כאוסף נקודות במישור הנמצאות בהצטלבויות של קווי האורך והרוחב השלמים.:\[
L:=\left\{ \left(x,y\right)\in\MKinteger^{2}\mid0<x\leq\frac{q-1}{2},\ 0<y\leq\frac{p-1}{2}\right\}
\]מהגדרה מתקיים \(\left|L\right|=\frac{q-1}{2}\cdot\frac{p-1}{2}\). נסמן:\[\begin{align*}
L_{1} & :=\left\{ \left(x,y\right)\in L\mid\frac{p}{q}\cdot x\geq y\right\} \\
L_{2} & :=\left\{ \left(x,y\right)\in L\mid\frac{p}{q}\cdot x\leq y\right\}
\end{align*}\]מהגדרה מתקיים \(L=L_{1}\cup L_{2}\), אך יתרה מזאת זהו איחוד זר מפני שלו הייתה קיימת נקודה \(\left(x,y\right)\in L\) כך ש-\(\frac{p}{q}\cdot x=y\) היינו מקבלים ש-\(q\mid x\) בסתירה לכך ש-\(0<x\leq\frac{q-1}{2}\); א"כ מתקיים \(\left|L\right|=\left|L_{1}\right|+\left|L_{2}\right|\). לכל \(\frac{p-1}{2}\geq i\in\MKnatural\) ולכל \(\frac{q-1}{2}\geq j\in\MKnatural\) מתקיים:\[\begin{align*}
\left|\left\{ \left(x,y\right)\in L_{1}\mid y=i\right\} \right| & =\left\lfloor \frac{i\cdot q}{p}\right\rfloor \\
\left|\left\{ \left(x,y\right)\in L_{2}\mid x=j\right\} \right| & =\left\lfloor \frac{j\cdot p}{q}\right\rfloor
\end{align*}\]\[\begin{align*}
\Rightarrow t_{2}:=\left|L_{2}\right| & =\sum_{i=1}^{\frac{p-1}{2}}\left\lfloor \frac{i\cdot q}{p}\right\rfloor \\
\Rightarrow t_{1}:=\left|L_{1}\right| & =\sum_{j=1}^{\frac{q-1}{2}}\left\lfloor \frac{j\cdot p}{q}\right\rfloor
\end{align*}\]נזכור שע"פ הלמה האחרונה (4.8) מתקיים:\[\begin{align*}
\left(\begin{array}{c}
q\\
\hline p
\end{array}\right) & =\left(-1\right)^{t_{2}}\\
\left(\begin{array}{c}
p\\
\hline q
\end{array}\right) & =\left(-1\right)^{t_{1}}
\end{align*}\]\[\begin{align*}
\Rightarrow\left(\begin{array}{c}
q\\
\hline p
\end{array}\right)\cdot\left(\begin{array}{c}
p\\
\hline q
\end{array}\right) & =\left(-1\right)^{t_{2}+t_{1}}=\left(-1\right)^{\left|L_{2}\right|+\left|L_{1}\right|}\\
& =\left(-1\right)^{\left|L\right|}=\left(-1\right)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}
\end{align*}\]
טענה 4.14. יהי \(2<p\in\MKprime\) ויהי \(a\in\MKinteger\) שארית ריבועית שונה מאפס מודולו \(p\), \(a\) הוא שארית ריבועית מודולו \(p^{k}\) לכל \(k\in\MKnatural\).
טענה 4.15. יהיו \(2<p,q\in\MKprime\) ו-\(a\in\left(\MKinteger/p\MKinteger\right)^{*}\), נתבונן בקונגרואנציה \(x^{q}\equiv a\mod p\);
אם \(p=q\) אז ע"פ המשפט הקטן של פרמה יש לקונגרואנציה פתרון יחיד והוא \(a\).
אם \(p\not\equiv1\mod q\) אז \(q\) זר ל-\(p-1\) ולכן יש לו הופכי מודולו \(p-1\) ומהמשפט הקטן של פרמה נקבל שקיים פתרון יחיד והוא \(a^{q^{-1}}\)46כאשר \(q^{-1}\) הוא ההופכי של \(q\) מודולו \(p-1\)..
אם \(p\equiv1\mod q\) נסמן ב-\(g\) שורש פרימיטיבי של \(p\) ויהי \(m\in\MKnatural\) כך ש-\(a\equiv g^{m}\mod p\), כעת יש לקונגרואנציה פתרון אם"ם \(q\mid m\)47נשים לב שיחס החלוקה הזה מוגדר היטב מפני ש-\(q\mid p-1\). ואז קבוצת הפתרונות היא:\[
\left\{ g^{\frac{m}{q}+k\cdot\frac{p-1}{q}}\mid q>k\in\MKnatural_{0}\right\}
\]
רוצים לפרגן לי על בניית האתר וכתיבת הסיכומים? אתם מוזמנים לתת טיפ.פורמטים נוספים:
#scrollButton {
position: fixed; /* Keeps the button in a fixed position */
bottom: 0.7em; /* Distance from the bottom */
right: 0.7em; /* Distance from the right */
height: 3.5em;
width: 3.5em;
cursor: pointer;
background-color: #084149;
opacity: 80%;
}
#scrollImage {
position: fixed; /* Keeps the button in a fixed position */
bottom: 0.7em; /* Distance from the bottom */
right: 0.7em; /* Distance from the right */
height: 3.5em;
width: 3.5em;
opacity: 80%;
}
function scrollToTop() {
window.scrollTo({ top: 0, behavior: 'smooth' });
}
דפי האתרדף הביתאודותצור קשרמפת אתרענפים מתמטייםהתחלהאנליזהאלגברהענפים נוספיםאקסיומת השלמותסיכומי הרצאות במתמטיקהדף הביתתרומהאודותהקדשהמפת אתרהתחלהאנליזהאלגברהענפים נוספיםצור קשרעודלאתר הקודםsrayaa.comעִבְלִיקְסתנ"ך ברויאר מוקלט
( function() {
var skipLinkTarget = document.querySelector( 'main' ),
sibling,
skipLinkTargetID,
skipLink;
// Early exit if a skip-link target can't be located.
if ( ! skipLinkTarget ) {
return;
}
/*
* Get the site wrapper.
* The skip-link will be injected in the beginning of it.
*/
sibling = document.querySelector( '.wp-site-blocks' );
// Early exit if the root element was not found.
if ( ! sibling ) {
return;
}
// Get the skip-link target's ID, and generate one if it doesn't exist.
skipLinkTargetID = skipLinkTarget.id;
if ( ! skipLinkTargetID ) {
skipLinkTargetID = 'wp--skip-link--target';
skipLinkTarget.id = skipLinkTargetID;
}
// Create the skip link.
skipLink = document.createElement( 'a' );
skipLink.classList.add( 'skip-link', 'screen-reader-text' );
skipLink.href = '#' + skipLinkTargetID;
skipLink.innerHTML = 'לדלג לתוכן';
// Inject the skip link.
sibling.parentElement.insertBefore( skipLink, sibling );
}() );